205 Link List
注意:拡張子の名前に従ってファイルを新規作成します.
hを押してファイルを作成したら、後で簡単に名前を変更します.cppファイルはコンパイルが間違っています.
シーケンステーブルの実装には6つのファイルが含まれています.
c 1.hは前処理コマンドである.
elemitype.h Elemtypeデータタイプを定義します.
c 2-2.hはLinkListのデータ構造である.
bo-nohead.cppはSqListの基本的な操作関数です.
function.h定義bo 2-2.cppにおいて、チェーンは関数ListTraverseに必要なアクセス関数を遍歴します.
main.cppは実現、テスト関数です.
hを押してファイルを作成したら、後で簡単に名前を変更します.cppファイルはコンパイルが間違っています.
シーケンステーブルの実装には6つのファイルが含まれています.
c 1.hは前処理コマンドである.
elemitype.h Elemtypeデータタイプを定義します.
c 2-2.hはLinkListのデータ構造である.
bo-nohead.cppはSqListの基本的な操作関数です.
function.h定義bo 2-2.cppにおいて、チェーンは関数ListTraverseに必要なアクセス関数を遍歴します.
main.cppは実現、テスト関数です.
//c1.h
#include<iostream>
#include<process.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
//elemtype.h
typedef int ElemType;
//c2-2.h
#ifndef C2_2_H
#define C2_2_H
#include"elemtype.h"
struct LNode
{
ElemType data;
LNode *next;
};
typedef LNode* LinkList;
void InitList(LinkList &L);
void ListTraverse(LinkList L, void(*vi)(ElemType));
Status ListInsert(LinkList &L, int index, ElemType e);
Status ListDelete(LinkList &L, int index, ElemType &e);
bool ListEmpty(LinkList L);
int ListLength(LinkList L);
Status GetElem(LinkList L, int index, ElemType &e);
int LocateElem(LinkList L, ElemType e);
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e);
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e);
void ClearList(LinkList &L);
void DestroyList(LinkList &L);
#endif
//bo-nohead.cpp
#include"c1.h"
#include"c2-2.h"
using namespace std;
void InitList(LinkList &L)
{
L = nullptr;
}
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
int i = 0;
if (L)
{
LinkList p = L;
while (p)
{
vi(p->data);
p = p->next;
i++;
if (!(i % 10))
cout << endl;
}
cout << endl;
}
}
Status ListInsert(LinkList &L, int index, ElemType e)
{
int j = 1;
LinkList p = L, s;
if (index < 1)
return ERROR;
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
if (index == 1)
{
s->next = L;
L = s;
}
else
{
while (p && j < index - 1)
{
p = p->next;
j++;
}
if (!p)
return ERROR;
s->next = p->next;
p->next = s;
}
return OK;
}
Status ListDelete(LinkList &L, int index, ElemType &e)
{
int j = 1;
LinkList p = L, q;
if (index == 1)
{
L = p->next;
e = p->data;
free(p);
return OK;
}
else
{
while (p->next && j < index - 1)
{
p = p->next;
j++;
}
if (!p->next || j > index - 1)
return ERROR;
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
}
bool ListEmpty(LinkList L)
{
if (L)
return false;
else
return true;
}
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L;
while (p)
{
i++;
p = p->next;
}
return i;
}
Status GetElem(LinkList L, int index, ElemType &e)
{
if (index < 1)
return ERROR;
int j = 1;
LinkList p = L;
while (p && j < index)
{
p = p->next;
j++;
}
if (!p)
return ERROR;
e = p->data;
return OK;
}
int LocateElem(LinkList L, ElemType e)
{
int i = 0;
LinkList p = L;
while (p)
{
i++;
if (p->data == e)
return i;
p = p->next;
}
return 0;
}
/*
//this function is not efficient
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
int location = LocateElem(L, cur_e);
if (location > 1)
{
GetElem(L, location - 1, pre_e);
return OK;
}
else
return ERROR;
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
int location = LocateElem(L, cur_e);
if (location >= 1 && location < ListLength(L))
{
GetElem(L, location + 1, next_e);
return OK;
}
else
return ERROR;
}
*/
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
LinkList p = L, q ;
while (p->next)
{
q = p->next;
if (q->data == cur_e)
{
pre_e = p->data;
return OK;
}
p = q;
}
return ERROR;
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
if (L)
{
LinkList p = L;
while (p->next)
{
if (p->data == cur_e)
{
next_e = p->next->data;
return OK;
}
p = p->next;
}
}
return ERROR;
}
void ClearList(LinkList &L)
{
LinkList p;
while (L)
{
p = L;
L = L->next;
free(p);
}
}
void DestroyList(LinkList &L)
{
LinkList q;
while (L)
{
q = L->next;
free(L);
L = q;
}
}
//function.h
#ifndef FUNCTION_CPP
#define FUNCTION_CPP
#include"c1.h"
#include"elemtype.h"
using namespace std;
void print(ElemType e)
{
cout << e << " ";
}
#endif
//main.cpp
#include "c1.h"
#include "c2-2.h"
#include "function.h"
using namespace std;
int main()
{
LinkList L;
InitList(L);
cout << "ListEmpty: " << ListEmpty(L) << endl;
cout << "ListLength: " << ListLength(L) << endl;
for (int i = 0; i < 100; i++)
cout << ListInsert(L, i + 1, i);
cout << endl;
ListTraverse(L, print);
cout << "ListEmpty: " << ListEmpty(L) << endl;
cout << "ListLength: " << ListLength(L) << endl;
cout << endl;
ElemType e;
ListDelete(L, 1, e);
ListDelete(L, 97, e);
ListTraverse(L, print);
cout << endl;
cout << "ListLength: " << ListLength(L) << endl;
cout << "GetElem: " << GetElem(L, 98, e);
cout << " e = " << e << endl;
cout << "LocateElem: " << LocateElem(L, 99) << endl;
cout << "PriorElem: " << PriorElem(L, 99, e);
cout << " e = " << e << endl;
cout << "NextElem: " << NextElem(L, 98, e);
cout << " e = " << e << endl;
ClearList(L);
DestroyList(L);
cin.get();
return 0;
}
142