单链表
一.插入和删除结点操作
1.插入s指向的结点
s->next = p->next; p->next = s;
2.删除结点
q = p->next; //临时保存被删结点 p->next = q->next; //从链表中删除结点q free(q); //释放结点q的空间
二、建立单链表
1.头插法
void CreateListF(LinkNode *&L,ElemType a[],int n) { int i; LinkNode *s; L = (LinkNode *)malloc(sizeof(LinkNode)); L->next = NULL; //创建头结点,其next域设置为NULL for(i=0;i<n;i++) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = a[i]; //循环建立数据结点s s->next = L->next; //将结点s插入到原首结点之前、头结点之后 L->next = s; }
2.尾插法
void CreateListR(LinkNode *&L,ElemType a[],int n) { int i; LinkNode *s,*r; L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点 r = L; //r始终指向尾结点,初始时指向头结点 for(i=0;i<n;i++) //循环建立数据结点 { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = a[i]; //创建数据结点s r->next = s; //将结点s插入到结点r之后 r = s; } r->next = NULL; //尾结点的next域置为NULL }
三.线性表基本运算在单链表中的实现
1.初始化线性表
void InitList(LinkNode *&L) { L = (LinkNode *)malloc(sizeof(LinkNode)); L->next = NULL; //创建头结点,其next域置为NULL }
2.销毁线性表
void DestroyList(LinkNode *&L) { LinkNode *pre = L,*p = L->next; //pre指向结点p的前驱结点 while(p != NULL) ;扫描单链表L { free(pre); //释放pre结点 pre = p; //pre、p同步后移一个结点 p = pre->next; } free(pre); //循环结束时p为NULL,pre指向尾结点,释放它 }
3.判断线性表是否为空表
bool ListEmpty(LinkNode *L) { return(L->next == NULL); }
4.求线性表的长度
int ListLength(LinkNode *L) { int n=0; LinkNode *p = L; //p指向头结点,n置为0 while(p->next != NULL) { n++; p = p->next; } return(n); }
5.输出线性表
void DispList(LinkNode *L) { LinkNode *p = L->next; while(p != NULL) { printf("%d ",p->data); p = p->next; } printf("\n"); }
6.求线性表中的某个数据元素值
bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0 LinkNode *p = L; if(i <= 0) return false; while(j<i && p!=NULL) { j++; p = p->next; } if(p == NULL) return false; else { e = p->data; return false; } }
7.按元素值查找
int LocateElem(LinkNode *L,ElemType e) { int i=1; LinkNode *p = L->next; while(p!=NULL && p->data!=e) { p = p->next; i++; } if(p == NULL) return(0); else return(i); }
8.插入数据元素
bool ListInsert(LinkNode *&L,int i,ElemType e) { int j=0; LinkNode *p = L,*s; if(i <= 0) return false; while(j<i-1 && p!=NULL) { j++; p = p->next; } if(p == NULL) return false; else { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = e; s->next = p->next; p->next = s; return true; } }
9.删除数据元素
bool ListDelete(LinkNode *&L,int i,ElemType &e) { int j=0; LinkNode *p = L,*q; if(i <= 0) return false; while(j<i-1 && p!=NULL) { j++; p = p->next; } if(p == NULL) return false; else { q = p->next; if(q == NULL) return false; e = q->data; p->next= q->next; free(q); return true; } }
四.单链表的应用示例
1.将一个带头结点的单链表L,拆分成两个带头结点的单链表L1和L2,要求L1使用L的头结点
void split(LinkNode *&L,LinkNode *&L1,LinkNode *&L2) { LinkNode *p = L->next,*q,*r1; L1 = L; r1 = L1; L2 = (LinkNode *)malloc(sizeof(LinkNode)); L2->next = NULL; while(p != NULL) { r1->next = p; //采用尾插法将p插入L1中 r1 = p; p = p->next; q = p->next; p->next = L2->next; //采用头插法将结点p插入L2中 L2->next = p; p = q; } r1->next = NULL; }
2.设计一个算法,删除一个单链表L中元素值最大的结点(假设这样的结点唯一)
void delmaxnode(LinkNode *&L) { LinkNode *p=L->next,*pre=L,*maxp=p,*maxpre=pre; while(p != NULL) { if(maxp->data < p->data) //若找到一个更大的结点 { maxp = p; //更新maxp maxpre = pre; //更新maxpre } pre = p; p = p->next; } maxpre->next = maxp->next; //删除maxp结点 free(maxp); //释放maxp结点 }
3.有一个带头结点的单链表L(至少有一个数据结点),设计一个算法使其元素递增有序排列
void sort(LinkNode *&L) { LinkNode *p,*pre,*q; p = L->next->next; L->next->next = NULL; while(p != NULL) { q = p->next; pre = L; while(pre->next!=NULL && pre->next->data < p->data) pre = pre->next; p->next = pre->next; pre->next = p; p = q; }
双链表
一.建立双链表
1.头插法:
void CreateListF(DLinkNode *&L,ElemType a[],int n) { DLinkNode *s; int i; L = (DLinkNode *)malloc(sizeof(DLinkNode)); //创建头结点 L->prior = L->next = NULL; for(i=0;i<n;i++) { s = (DLinkNode *)malloc(sizeof(DLinkNode)); s->data = a[i]; s->next = L->next; //将s结点插入到头结点之后 if(L->next != NULL) //若L存在数据结点,修改L->next的前驱指针 L->next->prior = s; L->next = s; s->prior = L; } }
2.尾插法
void CreateListR(DLinkNode *&L,ElemType a[],int n) { DLinkNode *s,*r; int i; L = (DLinkNode *)malloc(sizeof(DLinkNode)); r = L; for(i=0;i<n;i++) { s = (DLinkNode *)malloc(sizeof(DLinkNode)); s->data = a[i]; r->next = s; s->prior = r; r = s; } r->next = NULL; }
二.线性表基本运算在双链表中的实现
1.插入结点
bool ListInsert(DLinkNode *&L,int i,ElemType e) { int j=0; DLinkNode *p = L,*s; if(i <= 0) return false; while(j<i-1 && p!=NULL) { j++; p = p->next; } if(p == NULL) return false; else { s = (DLinkNode *)malloc(sizeof(DLinkNode)); s->data = e; s->next = p->next; if(p->next != NULL) p->next->prior = s; s->prior = p; p->next = s; return true; } }
2.删除结点
bool ListDelete(DLinkNode *&L,int i,ElemType &e) { int j=0; DLinkNode *p=L,*q; if(i <= 0) return false; while(j<i-1 && p!=NULL) { j++; p = p->next; } if(p == NULL) return false; else { q = p->next; if(q == NULL) return false; e = q->data; p->next = q->next; if(p->next != NULL) p->next->prior = p; free(q); return true; } }
三.应用示例
1.有一个带头结点的双链表L,设计一个算法将其所有元素逆置,即第1个元素变为最后一个元素,第2个元素变为倒数第2个元素......最后一个元素变为第1个元素
void reverse(DLinkNode *&L) { DLinkNode *p=L->next,*q; L->next = NULL; //构造只有头结点的双链表L while(p != NULL) { q = p->next; p->next = L->next; //采用头插法将p结点插入到双链表中 if(L->next != NULL) L->next->prior = p; L->next = p; //将新结点作为首结点 p->next = L; p = q; } }
2.有一个带头结点的双链表L(至少有一个数据结点),设计一个算法使其元素递增有序排列
void sort(DLinkNode *&L) { DLinkNode *p,*pre,*q; p = L->next->next; L->next->next = NULL; //构造只含一个数据结点的有序表 while(p != NULL) { q = p->next; pre = L; while(pre->next!=NULL && pre->next->data<p->data) pre = pre->next; p->next = pre->next; if(pre->next != NULL) pre->next->prior = p; pre->next = p; p->prior = pre; p = q; } }
循环链表
与单链表的区别在于将它的尾结点next指针域由原来为空改为指向头结点。