数据结构线性表

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2

typedef int Status;

1线性表的顺序表示和实现 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{

ElemType *Elem; int length; int listsize; }SqList;

Status InitList_Sq(SqList &L){ //构造一个空的线性表L

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); If (L.elem==NULL)

exit(OVERFLOW); else {

L.length=0;

L.listsize=LIST_INIT_SIZE; return OK; } }

Status DestroyList_Sq(SqList &L) {//销毁线性表L if(L.elem==NULL) return ERROR; else

free(L.elem); return OK; }

Status ClearList_Sq(Sqlist &L) {//将L置为空表 if(L.elem==NULL)

exit(ERROR); int i;

ElemType *p_elem=L.elem; for(i=0;i<L.length;i++) {

*L.elem=NULL; L.elem++; }

L.elem=p_elem; return OK; }

Status ListEmpty_Sq(SqList L)

{//若L为空表则返回TRUE，否则返回FALSE int i;

ElemType *p_elem=L.elem; for(i=0;i<L.length;i++) {

if(*Elem!=0) {

L.elem=p_elem; return FALSE; }

L.elem++; }

return TRUE; }

Status ListLength_Sq(SqList L) {//返回L中元素个数 return L.length; }

Status GetElem_Sq(SqList &L,int i,ElemType &e)

{//用e返回L中第i个数据元素的值 int j;

ElemType *p_elem=L.elem; if(i<1||i>L.length)

return OVERFLOW; for(j=1;j<=I;j++)

L.elem++;

e=*L.elem; L.elem=p_elem; return OK; }

Status LocateElem_Sq(SqList &L,ElemType e,Status(*compare)(ElemType,ElemType)) {//返回L中第一个与e满足关系compare()的数据元素的位序，若这个数据元素不存在，个，则用next_e返回它的前驱，否则操作失败，next_e无定义 ElemType *p_elem; int i,j;

i=LocateElem_Sq(L,cur_e); if(i<1||i>=L.length) exit(OVERFLOW); for(j=1;j<1;j++) {

则返回0 i=1;

p=L.elem;

while(i<=L.length&&!(*compare)(*p++,e)) ++i;

if(i<=L.length return i; else return 0; }

Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType &pre_e)

{//若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 p=L.elem; int i,j;

i=LocationElem_Sq(L,cur_e); if(i<=1||i>L.length)

exit(OVERFLOW); for(j=1;j<I;j++) {

if(j==(i-1)) {

pre_e=L.elem; L.elem=p; return OK; } else

L.elem++; } }

Status NextElem_Sq(SqList L,ElemType cur_e,ElemType &next_e)

{//若cur_e是L的数据元素，且不是最后一 if(j==(i-1)) {

next_e=L.elem; L.elem=p_elem; return OK; } else

L.elem++; } }

Status ListInsert_S (List_Sq &L, int i, ElemType e){

if(i<1 || i>L.length+1) return ERROR; //若i为无效值，返回错误

if(L.length= =L.maxsize){ //若存储容量已满，则增加分配空间

newbase=(ElemType *) realloc(L.list,

(L.maxsize+LIST_INCREASE)*sizeof(ElemType));

if(!newbase) exit(OVERFLOW); //若增加分配空间失败，退出程序 L.list= newbase; //新基址

L.maxsize +=LIST_INCREASE; //存储容量增加 }//if

q=&(L.list[i–1]); // 插入位置。q=L.list+i–1;也可。

for(p =&(L.list[L.length–1]); p>=q; – –p) // p=L.list+ L.Length–1; 也可。

*(p+1) = *p; //将插入元素位置之后的元素依次后移一个位置 *q=e; //插入元素e

++ L.length; //线性表长度增加1

return OK; //插入操作成功 }//ListInsert_S

Status ListDelete_S (List_Sq &L, int i, LinkList q; while(L) {

q=L->next; ElemType &e){

if(i<1 || i>L.length) return ERROR; //若i为无效值，返回错误

p=&(L.list[i–1]); //被删元素的位置，p=L.list+i–1;也可

e=*p; //通过e返回被删除的元素的值 q=L.list+ L.length–1; //线性表的最后一个元素的位置

for(++p; p<=q; ++p ) *(p–1) =*p; //被删除元素之后的元素依次前移

– –L.length; //线性表长度减少1 return OK; //删除操作成功 }//ListDelete_S

void ListTraverse_Sq(SqList L,visit)

{//依次对L的每个数据元素调用函数visit(),一旦visit()失败，则操作失败 for(int i=1;i<L.length+1;i++) return visit(Elem[i-1]); }

2线性表的链式表示和实现

2.1带头节点的线性表的单链表存储结构 typedef struct LLNode{ ElemType data; struct LLNode *next; }LLNode,*LinkList;

Status InitList_L(LinkList &L) {

L=(LinkList)malloc(sizeof(struct

LLNode)); if(!L)

exit(OVERFLOW); L->next=NULL; returnOK; }

Status DestroyList_L(LinkList &L) { free(L); L=q; }

return OK; }

Status ClearList_L(LinkList &L) {

LinkList p,q; while(p) {

q=p->next; free(p); p=q; }

L->next=NULL; return OK; }

Status ListEmpty_L(LinkList L) {

if(L->NEXT) return FALSE; else

return TRUE; }

Status ListLength_L(LinkList L) {

int i=0;

LinkList p=L->next; while(p) { i++;

p=p->next; }

return I; }

Status GetElem_L(LinkList L,int I,ElemType

&e)

{

int j=1;

LinkList p=L->next; while(p&&j<i) {

p=p->next; j++; }

if(!p||j>i)

return ERROR; e=p->data; return OK; }

Status LocateElem_L(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) {

int i=0;

LinkList p=L->next; while(p) {

i++;

if(compare(p->data,e)) return i; p=p->next; }

return 0; }

Status PriorElem_L(LinkList L,ElemType cur_e,ElemType &pre_e) {

LinkList p,q=L->next; while(p->next) {

q=p->next;

if(q->data==cur_e) {

pre_e=p->data; return OK; } p=q; }

return INFEASIBLE; }

Status NextElem_L(LinkList L,ElemType cur_e,ElemType &next_e) {

LinkList p=L->next; while(p->next) {

if(q->data==cur_e) {

next_e=p->next->data; return OK; }

p=p->next; }

ruturn INFEASIBLE; }

Status ListInsert_L(LinkList &L,int i,ElemType e)

{//在L中的第i个位置插入新的数据元素e,L的长度加1 int j=0;

LinkList p=L,s; while(p&&j<i-1) {

p=p->next; j++; }

if(!p||j>i-1) return ERROR else {

s=(LinkList)malloc(sizeof(struct LLNode));

s->data=e;

s->next=p->next; p->next=s; return OK } }

Status ListDelete_L(LinkList &L,int i,ElemType &e)

{//删除L的第i个元素，并用e返回其值，

L的长度减1 int j=0;

LinkList p=L,q;

while(p->next&&j<i-1) {

p=p->next; j++; }

if(!p->next||j>i-1)

return ERROR; q=p->next; e=q->data;

p->next=q->next; free(q); return OK; }

Status ListTraverse_L(LinkList L) {

LinkList p=L->next; while(p) {

printf(“%d”,p->data); p=p->next; }

printf(“\n”); return OK; }

2.2不带头结点的单链线性表结构 void InitList_L(LinkList &L) {

L=(LinkList)malloc(sizeof(LLNode)); L->next=NULL; }

struct LLNode *initlist(void) { int n,i; struct LLNode *head,*p,*ph;/*PH是辅助指针，P向后移动，用PH串联起来*/ head=(struct

LLNode*)malloc(sizeof(struct LLNode)); if(head==NULL) { printf("malloc error!!!!");

return 0; } head->next=NULL; ph=head;

for(i=1;i<=n-1;i++) {

p=(struct

LLNode*)malloc(sizeof(struct LLNode)); if(p==NULL) { printf("malloc errror\n"); return 0; } ph->next=p; ph=p;

}/*用PH将后面的结点连接起来*/ p->next=NULL; return head; }

void typeelem(struct LLNode *head) { int i; struct LLNode *p; p=head;

//printf("%d",head->length);

printf("type in your element!!as long as it is init!!\n"); do { scanf("%d",&(p->num)); p=p->next; }while(p->next!=NULL); scanf("%d",&(p->num)); }

void printlist(struct LLNode *head) { int i; struct LLNode *p; p=head;

do { printf("%4d",p->num); p=p->next; }while(p->next!=NULL); printf("%4d",p->num);

printf("\n***********************************\n"); }

void clearlist(struct LLNode *head) {

int i;

struct LLNode *ph; ph=head;

while(ph->next!=NULL) {

ph->num=0; ph=ph->next; }; ph->num=0; }

int listempty(struct LLNode *head) {

if(head->next==NULL) return 1; else

return 0; }

int getelem(struct LLNode *head,int n) {

struct LLNode *ph; int i; ph=head;

for(i=1;i<=n-1;i++) ph=ph->next; return ph->num; }

int listlength(struct LLNode *head) { int k=0;

struct LLNode *ph; ph=head;

while(ph->next!=NULL) {

k++;

ph=ph->next; } k++; return k;

}

int priorelem(struct LLNode *head,int num) {

struct LLNode *ph,*pb; ph=head;

if(num==ph->num) {

printf("no prior\n"); exit(0); }

pb=ph;

ph=ph->next; do {

if(ph->num==num) return pb->num; else {

pb=ph;

ph=ph->next; }

}while(ph->next!=NULL); return pb->num;

printf("cannot find\n"); }

int nextelem(struct LLNode *head,int num) {

struct LLNode *ph,*pf; ph=head;

pf=ph->next;

while(ph->next!=NULL)

{

if(ph->num==num) return pf->num; else {

pf=ph->next; ph=ph->next; } };

printf("cannot find"); }

void listinsert(struct LLNode *head,int loc,int num) { int i;

struct LLNode *ph,*pnew,*p; ph=head;

for(i=1;i<=loc-2;i++) ph=ph->next; pnew=(struct

LLNode*)malloc(sizeof(struct LLNode)); pnew->num=num; p=ph->next; ph->next=pnew; pnew->next=p; }

int listdelete(struct LLNode*head,int loc) {

int i,num;

struct LLNode *ph,*p; ph=head;

for(i=1;i<=loc-2;i++) ph=ph->next; p=ph->next; num=p->num;

ph->next=ph->next->next; free(p); return num; }

int compare(int a,int b) { if(a==(b+1)) return 1; else

return 0; }

int locateelem(struct LLNode *head,int n,int compare(int a,int b))/*找到表中比输入元素大一元素的位序*/ {

struct LLNode *p; int k=0; p=head;

while(p->next!=NULL) { k++;

if(compare(p->num,n)) return k+1; p=p->next; }

if(compare(p->num,n)) return k+2; return 0; }

void visit(int n) {

if((n/2.0-n/2)==0)

printf("%d是偶数\n",n); }

void listtraverse(struct LLNode *head,void visit(int n)) {

struct LLNode *p; p=head;

while(p->next!=NULL) {

visit(p->num); p=p->next; }

visit(p->num);

}

void destroylist(struct LLNode *head) {

struct LLNode *p,*ph; p=head; ph=head;

while(p->next!=NULL) {

ph=p->next; free(p); p=ph; }

free(p);

head->next=NULL; }

3 静态链表的基本操作 3.1 带头节点的静态链表

int Malloc(SLinkList space)//若备用链表不空，则返回分配的结点下标

{ int i=space[0].cur;//备用链表第1个结点的位置

if(i)//备用链表不空

space[0].cur=space[i].cur;//备用链表的头结点指向原备用链表的第2个结点 return i; }

void Free(SLinkList space,int k)

{ //将下标为k的空闲结点回收到备用链表中

space[k].cur=space[0].cur;//回收结点的“游标”指向备用链表的第1个结点

space[0].cur=k;//备用链表的头结点指向新回收的结点 }

void InitList(SLinkList L) { //构造一个空的链表L，表头为L的最后一个单元L[MAX_SIZE_1],其他单元链成一个备用链表，表头为L的第一个单元L[0],"0"表示空指针 int i; L[MAX_SIZE-1].cur=0;//L的最后一个单元为空链表的表头

for(i=0;i<MAX_SIZE-2;i++)//将其他单元链接成以L[0]为表头的备用链表 L[i].cur=i+1;

L[MAX_SIZE-2].cur=0; }

void ClearList(SLinkList L) { //将表置空

int j,k,i=L[MAX_SIZE-1].cur;//i指向链表的第1个结点的位序

L[MAX_SIZE-1].cur=0;//链表为空

k=L[0].cur;//备用链表第i个结点的位置 L[0].cur=i;//把链表的结点连到备用链表的表头

while(i)//未到表尾

{j=i;//j指向当前结点的位置 i=L[i].cur; }

L[j].cur=k;//备用链表的第i个结点接到链表的尾部 }

Status ListEmpty(SLinkList L) { //判断表是否为空

if(L[MAX_SIZE-1].cur==0)//空表 return TRUE; else return FALSE; }

int ListLength(SLinkList L) { //返回表的长度

int j=0,i=L[MAX_SIZE-1].cur;//i指向链表的第1个结点的位序

while(i)//未到链表的表尾

{ i=L[i].cur;//i指向下一个结点 j++;//计数器加1 } return j; }

Status GetElem(SLinkList L,int i,ElemType &e)

{ //用e返回L中第i个元素的值

int m,k=MAX_SIZE-1;//k指向表头结点的

位序

if(i<1||i>ListLength(L)) //不存在第i个元素 } }

return ERROR;

for(m=1;m<=i;m++)//k向后移动到第i个元素

k=L[k].cur;//指向下一个元素 e=L[k].data; return OK; }

int LocateElem(SLinkList L,ElemType e)//在静态链表中找第1个值为e的元素，若找到返回其位序

{ int i=L[MAX_SIZE-1].cur;//i指向表中的第1个结点的位序

while(i&&L[i].data!=e)//在表中查找 i=L[i].cur;//指向下一个元素 return i; }

Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e) { //寻找前驱

int j,i=L[MAX_SIZE-1].cur;//i指向链表第1个结点的位置 do //向后移结点

{ j=i;//j指向i所指元素

i=L[i].cur;//i 指向下一个元素 }while(i&&cur_e!=L[i].data); if(i)//找到该元素 { pre_e=L[j].data; return OK; }

else return ERROR; }

Status NextElem(SLinkList L,ElemType cur_e,ElemType &next_e)

{ int j,i=LocateElem(L,cur_e);//在L中查找第1个值为cur_e的元素位置 if(i)

{ j=L[i].cur; if(j)

{ next_e=L[j].data; return OK; return ERROR; }

Status ListInsert(SLinkList L,int i,ElemType e)

{ //在L中第i个元素之前插入数据元素e int m,j,k=MAX_SIZE-1;//k指示表头结点的位序

if(i<1||i>ListLength(L)+1) return ERROR;

j=Malloc(L);//申请新单元 if(j)//申请成功 { L[j].data=e;

for(m=1;m<i;m++)//k向后移i-1个结点，使k指示第i-1个结点

k=L[k].cur;//指向下一个结点

L[j].cur=L[k].cur;//新结点指向第i-1个元素后的元素

L[k].cur=j;//第i-1个元素指向新单元 return OK; }

return ERROR; }

Status ListDelete(SLinkList L,int i,ElemType &e)

{ //删除L中第i个元素，并返回其值 int j,k=MAX_SIZE-1;//k指示表头结点的位置

if(i<1||i>ListLength(L))// return ERROR;

for(j=1;j<i;j++)//移动i-1个元素，使k指向第i-1个元素

k=L[k].cur;//指向下一个元素 j=L[k].cur;//待删除元素

L[k].cur=L[j].cur;//使第i-1个元素指向待删除元素的后继元素 e=L[j].data; Free(L,j); return OK;

} void ListTraverse(SLinkList newLNode->next=head; head=newLNode; L,void(*visit)(ElemType))

{//依次对表中的元素调用函数visit()

int i=L[MAX_SIZE-1].cur;//i指向第一个元素的位序 while(i)

{ visit(L[i].data);//对当前元素调用visit() i=L[i].cur;//指向下一个元素 }

printf("\n"); }

void print1(ElemType e) { printf("%3d",e); }

3.2不带头结点的静态链表

List*delete_list(List*head,int data); int main() {

List*head=NULL; int i;

// for(i=0;i<10;i++)

// head=insert_list_2nd(head,i); // head=insert_list_last(head,i); for(i=9;i>=0;i--)

head=insert_list_order(head,i); print_list(head); for(i=0;i<9;i++)

head=delete_list(head,i); print_list(head); }

List*insert_list_2nd(List*head,int data) {

List*newLNode=(List*)malloc(sizeof(List)); newLNode->data=data; /* if(head==NULL) {

head=newLNode;

newLNode->next=NULL; } else { }*/

newLNode->next=head; head=newLNode; return head; }

List*insert_list_last(List*head,int data)

{ List*newLNode=(List*)malloc(sizeof(List));

List*temp=head;

newLNode->data=data; newLNode->next=NULL;

if(head==NULL) return newLNode; while(temp->next) {

temp=temp->next; }

temp->next=newLNode; return head; }

List*insert_list_order(List*head,int data) {

List*temp=head;

List*newLNode=(List*)malloc(sizeof(List)); newLNode->data=data; newLNode->next=NULL;

if(head==NULL) //链表为空为空 {

return newLNode; }

if(head->data>data)//链表第一个节点就是要插入的位置 {

newLNode->next=head; return newLNode; }

while(temp->next && temp->next->data<data) {

temp=temp->next; }

/* if(temp->next==NULL) {

temp->next=newLNode; } else {

newLNode->next=temp->next; temp->next=newLNode; }*/

newLNode->next=temp->next; temp->next=newLNode; return head; }

void print_list(List*head) {

while(head) {

printf("%d\n",head->data); head=head->next; } }

List*delete_list(List*head,int data) { List*temp; List*p;

if(head==NULL) return NULL; if(head->data==data) {

temp=head->next; free(head); return temp; }

temp=head;

while(temp->next

temp->next->data!=data) {

temp=temp->next; }

//p=temp->next;

if(temp->next==NULL) {

printf("no have %d\n",data); return head; } else {

p=temp->next;

temp->next=temp->next->next; free(p); return head; } }

4循环链表的基本操作 4.1 带头节点的循环链表 void InitList(LinkList &L) { //初始化

L=(LinkList)malloc(sizeof(LLNode));//产生结点 if(!L)

exit(OVERFLOW);

L->next=L;//头结点的指针指向头结点 }

void ClearList(LinkList &L) { LinkList p,q;

L=L->next;//L指向头结点 p=L->next;//p指向第1个结点 while(p!=L)

{ q=p->next;//q指向p的后继 free(p);

p=q;//p指向q所指结点 }

L->next=L;//头结点指针指向自身 }

void DestroyList(LinkList &L) { //ClearList(L); &&

LinkList p,q;

L=L->next;//L指向头结点 p=L->next;//p指向第1个结点 while(p!=L)

{ q=p->next;//q指向p的后继 free(p);

p=q;//p指向q所指结点 }

L->next=L;//头结点指针指向自身

free(L); L=NULL; }

Status ListEmpty(LinkList L) {

if(L->next==L) return TRUE; else return FALSE; }

int ListLength(LinkList L) {

int i=0;

LinkList p=L->next;//p指向头结点 while(p!=L) {

i++;//计数器加1 p=p->next; }

return i; }

Status GetElem(LinkList L,int i,ElemType &e)

{ //当第i个元素存在时，将其值赋给e int j=1;

LinkList p=L->next->next;//p指向第一个元素

if(i<0||i>ListLength(L)) return ERROR; while(j<i)

{

j++;

p=p->next; }

e=p->data; return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) {//返回第1个与e满足关系compare()的数据元素的位序 int i=0;

LinkList p=L->next->next;//p指向第1个结点

while(p!=L->next)

{

i++;//计数器加1 if(compare(p->data,e)) return i; p=p->next; }

return 0; }

Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e) { //返回前驱

LinkList q,p=L->next->next;//p指向第一个元素

q=p->next;//q指向p的后继 while(q!=L->next) {

if(q->data==cur_e) {

pre_e=p->data; return OK; }

p=q;//p的后继不为cur_e向后移 q=q->next; }

return ERROR; } Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e) { //返回后继

LinkList p=L->next->next;//p指向第一个元素

while(p!=L) {

if(p->data==cur_e) {

next_e=p->next->data;//将P所指

的结点的后继后继的值赋给next_e return OK; }

p=p->next; }

return ERROR; }

Status ListInsert(LinkList &L,int i,ElemType e)

{

LinkList p=L->next,s; int j=0;

if(i<=0||i>ListLength(L)+1) return ERROR;

while(j<i-1) {

j++;

p=p->next;

}

s=(LinkList)malloc(sizeof(LLNode)); s->data=e;

s->next=p->next; p->next=s; if(p==L) L=s; return OK; }

Status ListDelete(LinkList &L,int i,ElemType &e) {

LinkList q,p=L->next; int j=0; if(!p||j>i-1)

return ERROR; while(j<i-1) {

j++;//计数器加1 p=p->next; }

q=p->next;

p->next=q->next; e=q->data; if(L==q) L=p; free(q); return OK; } void ListTraverse(LinkList L,void(* visit)(ElemType)) { LinkList p=L->next->next;//p指向表头结点

while(p!=L->next) {

visit(p->data); p=p->next; }

printf("\n"); }

ListTraverse(L,print);

printf("前驱判断\n"); for(i=1;i<=10;i++)

{ GetElem(L,i,e);//把L中第i个元素的值赋给e

k=PriorElem(L,e,e0);//判断e是否有前驱 if(k==0)

printf("元素%d无前驱\n",e); else

printf("元素%d的前驱为%d\n",e,e0); }

printf("后继判断\n"); for(i=1;i<=10;i++) { GetElem(L,i,e);

k=NextElem(L,e,e1); if(k==0)

printf("元素%d无后继\n",e); else

printf("元素%d的后继为%d\n",e,e1); }

5 双向链表的基本操作 5.1 带头节点的双向链表 void InitList(DuLinkList &L) {//产生空间的双向循环链表

L=(DuLinkList)malloc(sizeof(DuLLNode)); if(L)

L->next=L->prior=L; else

exit(OVERFLOW); }

void ClearList(DuLinkList L)

{ //清空链表

DuLinkList p=L->next;//p指向第一个结点

while(p!=L) {

p=p->next; free(p->prior); }

L->next=L->prior=L;//头结点的两个指针域指向其身 }

void DestroyList(DuLinkList &L) {

ClearList(L);//将L清空 free(L); L=NULL; }

Status ListEmpty(DuLinkList L) { //判断表是否为空

if(L->next==L&&L->prior==L) return TRUE; else

return FALSE; }

int ListLength(DuLinkList L) { //返回表的长度 int i=0;

DuLinkList p=L->next;//p指向第一个结点

while(p!=L) {

i++;

p=p->next; }

return i; }

Status GetElem(DuLinkList L,int i,ElemType &e)

{ //当第i个元素存在，将值赋给e int j=1;

DuLinkList p=L->next;//p指向第一个结点

while(p!=L&&j<i)//顺指针向后查找，直到p指向第i个元素 {

j++;

p=p->next; }

if(p==L||j>i)

return ERROR; e=p->data; return OK; }

int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { //返回表中第1个与e满足关系compare()的数据元素的位序 int i=0;

DuLinkList p=L->next;

while(p!=L)//p未指向头结点 {

i++;//计数器加1

if(compare(p->data,e))//找到这样的元素

return i;

p=p->next; }

return 0; }

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e) {

DuLinkList p=L->next->next;//p指向第2个元素

while(p!=L) {

if(p->data==cur_e)//p指向值为cur_e的结点

{

pre_e=p->prior->data;//将p的前驱

结点的值赋给

return OK;

}

p=p->next; }

return ERROR;

}

Status NextElem(DuLinkList L,ElemType s->data=e;//将e赋给新的结点

s->prior=p;//新结点的前驱为第i-1个结点

s->next=p->next;//新结点的后继为第i个cur_e,ElemType &next_e) {//返回后继

DuLinkList p=L->next->next;//p指向第二个元素

while(p!=L) {

if(p->prior ->data==cur_e)//p所指结点的前驱指向cur_e {

next_e=p->data;//将p所指结点的

值赋给next_e

return OK;

}

p=p->next; }

return ERROR; }

DuLinkList GetElemP(DuLinkList L,int i) {//在双向链表中返回第i个元素的地址 int j;

DuLinkList p=L;//p指向头结点 if(i<0||i>ListLength(L)) return NULL;

for(j=1;j<=i;j++)//p指向第i个结点 p=p->next;//p指向下一个结点 return p; }

Status ListInsert(DuLinkList L,int i,ElemType e)

{ //在链表第i个位置上插入元素 DuLinkList p,s;

if(i<1||i>ListLength(L)+1) return ERROR;

p=GetElemP(L,i-1);//在L中确定第i个结点前驱的位置指针p if(!p) return ERROR;

s=(DuLinkList)malloc(sizeof(DuLLNode));//生成新结点

if(!s) return ERROR; 结点

p->next->prior=s;//第i个结点的前驱指向新结点

p->next=s;//第i-1个结点的后继指向新结点

return OK; }

Status ListDelete(DuLinkList L,ElemType &e)

{ //删除第i个结点 DuLinkList p; int i; if(i<1)

return ERROR;

p=GetElemP(L,i);//在L中确定第i个元素的位置指针

if(!p) return ERROR;

e=p->data;//把第i个结点的元素的值赋给e

p->prior->next=p->next;//第原i-1个结点的后继指向原第i+1个结点

p->next->prior=p->prior;//第原i+1个结点的前驱指向原第i-1个结点 free(p); return OK; } void ListTraverse(DuLinkList L,void(*visit)(ElemType))

{//由双向循环链表的表头出发，正序对每个数据元素调用函数visit()

DuLinkList p=L->next;//p指向首元结点 while(p!=L) {

visit(p->data);//对p所指结点调用函数visit()

p=p->next; }

printf("\n");

} void ListTraverseBack(DuLinkList {

q=p->next; free(p); L,void(*visit)(ElemType))

{ //由双向循环链表的表头出发，逆序对每个元素调用函数visit()

DuLinkList p=L->prior;//p指向尾结点 while(p!=L) {

visit(p->data); p=p->prior; }

printf("\n"); }

5.2不带头结点的双向链表

typedef struct LNode {//结点结构 int data;

struct LNode *pre,*next;//前驱指针和后继指针

}LNode,*Link;

typedef struct List {//链表结构 Link head,tail; int length; }List,*LinkList;

LinkList InitList(void) {//构造一个空的链表 LinkList list; list=new List;

list->head=list->tail=NULL; list->length=0; return list; }

void ClearList(LinkList list)

{//清空链表，并释放每个结点的空间 Link p,q; p=list->head;

while(p!=list->tail) p=q; }

free(p);//释放尾结点

list->tail=list->head=NULL; list->length=0; }

void DestroyList(LinkList list) {

ClearList(list); free(list->head); free(list->tail); }

Status ListEmpty(List list) {

if(list.length==0) return TRUE; return FALSE; }

int ListLength(List list) {

return list.length; }

void InsertElemToList(LinkList list,int pos,int elem) {

Link p;

p=new LNode; p->data=elem;

if(pos<1 || pos>ListLength(*list)+1) cout<<"The position is invalidate."<<endl; else {

if(pos==1) {//插在表头

if(IsListEmpty(*list)) {

list->head=list->tail=p; p->next=NULL; } else {

p->next=list->head; list->head->pre=p; list->head=p; } }

else if(pos==ListLength(*list)+1) {//插在表尾

list->tail->next=p; p->pre=list->tail; list->tail=p; p->next=NULL; } else {

Link q=list->head; for(int i=1;i<pos-1;++i) {//找到pos-1位置的结点 q=q->next; }

p->next=q->next; p->pre=q;

q->next->pre=p; q->next=p; }

++list->length; } }

void DeleteElemFromList(LinkList list,int pos,int &elem) {

if(IsListEmpty(*list)) {

cout<<"The list is empty,you can't delete element."<<endl; } else {

if(pos<1 || pos>ListLength(*list)) {//删除位置不正确 cout<<"The position is invalidate."<<endl;

return;//如果条件不成立，就结束 } else {

if(pos==1) {//删除表头

if(ListLength(*list)==1) {//表长为1

Link p=list->head;

list->head=list->tail=NULL; elem=p->data; free(p); } else

{//表长大于1

Link p=list->head; list->head=p->next; p->next->pre=NULL; elem=p->data; free(p); } }

else if(pos==ListLength(*list)) {//删除表尾

Link q=list->tail; list->tail=q->pre;

list->tail->next=NULL; elem=q->data; free(q); } else {

Link p=list->head; for(int i=1;i<pos;++i) {//找到pos位置的结点 p=p->next; }

p->pre->next=p->next; p->next->pre=p->pre; elem=p->data; free(p);

}

--list->length; } } }

bool PreElem(List list,int pos,int &elem) {//判断 pos位置的结点有无前驱，若有则将其值存入elem

if(pos<1 || pos>ListLength(list)) {

cout<<"The position is invalidate."<<endl; return false; }

else {

if(pos==1) {

cout<<"This position doesn't have a pre_element."<<endl; return false; } else {

Link p=list.head; for(int i=1;i<pos;++i) {//找到pos位置处结点 p=p->next; }

elem=p->pre->data; return true; } } }

bool NextElem(List list,int pos,int &elem) {

if(pos<1 || pos>ListLength(list)) {

cout<<"The position is invalidate."<<endl; return false; } else {

if(pos==ListLength(list)) {

cout<<"This position doesn't have a next_element."<<endl; return false; } else {

Link p=list.head; for(int i=1;i<pos;++i) {//找到pos位置处结点 p=p->next; }

elem=p->next->data; return true; } } }

bool CurrentElem(List list,int pos,int &elem) {

if(pos<1 || pos>ListLength(list)) {

cout<<"The position is invalidate."<<endl; return false; } else {

Link p=list.head; for(int i=1;i<pos;++i) {

p=p->next; }

elem=p->data; return true; } }

bool GetHead(List list,int &elem) {//如果链表不空，则返回表头元素，用elem接收

if(IsListEmpty(list))

{

cout<<"The list is empty."<<endl; return false;

}

else

{

elem=list.head->data;

return true;

}

}

bool GetTail(List list,int &elem)

{//如果链表不空，则返回表尾元素，用elem接收

if(IsListEmpty(list))

{

cout<<"The list is empty."<<endl; return false;

}

else

{

elem=list.tail->data;

return true;

}

}

void VisitElemFromList(List list) {

Link p=list.head;

if(!IsListEmpty(list))

{

while(p)

{

cout<<p->data<<' ';

p=p->next;

}

cout<<endl;

}

}