简记"/>
数据结构简记
第 2 章 线性表
2.1 线性表的定义
线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为L=(a1,a2,···,ai,ai+1,···,an)，式中a1是唯一的第一个数据元素，又称表头元素；an是唯一的最后一个元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。
线性表的特点：
- 表中元素的个数有限
- 表中元素具有逻辑上的顺序性，表中元素有先后次序
- 表中元素都是数据元素，每个元素都是单个元素。
- 表中元素的数据类型都相同，即每个元素占有相同大小的存储空间。
- 表中元素具有抽象性，即仅讨论元素的逻辑关系，而不考虑元素的内容。
注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链表是指存储结构，两者属于不同层面的概念。
2.2 线性表的基本操作
- InitList(&L)：初始化表。构造一个空的线性表。
- Length(L)：求表长。返回线性表的L的 长度，即L中数据元素的个数。
- LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
- GetElem(L,i)：按位查找操作。获取表L中第 i 个位置的元素的值。
- ListInsert(&L,i,e)：插入操作。在表L中的第 i 个位置上插入指定元素e。
- ListDelete(&L,i,&e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
- PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
- DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
2.3 顺序表
2.3.1 顺序表的定义
线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储的是第 i+1 个元素，称 i 为元素ai在线性表中的位序。因此，顺序表的特点就是表中元素的逻辑顺序与其物理顺序相同。
假设线性表的元素类型为ElemType，则线性表的顺序存储类型描述为
#define MaxSize 50 //定义线性表的最大长度
typedef struct{ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义 注意：上机运行时需要将ElemType更换为具体的数据类型。
动态分配时，线性表的顺序存储类型描述为
#define InitSize 100 //表长度的初始定义
typedef struct{ElemType *data; //指示动态分配数组的指针int MaxSize,length; //数组的最大容量和当前个数
}SqList; //动态分配数组顺序表C的初始动态分配语句为
L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);C++的初始动态分配语句为
L.data = new ElemType[InitSize];2.3.2 顺序表上的基本操作
初始化操作
//方式一
void initlist(SqList *L)
{L->data = (ElemType*)malloc(sizeof(ElemType)*InitSize);L->length=0;L->MaxSize=InitSize;
}
//方式二
void initlist(SqList L)
{L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);L.length=0;L.MaxSize=InitSize;
}注意：使用*L时，用（L->）来取元素，使用L时，用（L.）来取元素。
求表长操作
int getlen(SqList *L)
{return L->length;
}取元素操作
int getelemz(SqList *L,int i,ElemType *e)
{if(i<1 || i>L->length)return 0;*e=L->data[i-1];return 1;
}元素定位操作
int LocateElem(SqList *L,ElemType e)
{int i;for(i=0;i<L->length;i++)if(L->data[i]==e)return i+1;return 0;
}插入操作
int ListInsert(SqList *L,int i,ElemType e)
{int j;if(i<1 || i>L->length+1) //判断i的范围是否有效return 0;if(L->length==L->MaxSize) //存储空间不够，增加一个存储空间{//重置存储空间长度L->data = (ElemType*)realloc(L->data,(L->length+1) * sizeof(ElemType));L->MaxSize++;}for(j=L->length;j>=i;j--)//将序号为i及之后的数据元素后移一位L->data[j]=L->data[j-1];L->data[i-1]=e; //在位置i处放入eL->length++; //顺序表长度加1return 1;
}删除操作
int ListDelete(SqList *L,int i,ElemType *e)
{int j;if(i<1 || i>L->length) //判断i的范围是否有效return 0;*e=L->data[i-1]; //将删除的元素赋值给efor(j=i;j<L->length;j++) //将第i个位置后的元素前移L->data[j-1]=L->data[j]; L->length--; //顺序表长度减1return 1;
}输出操作
void list(SqList *L)
{int i;for(i=0;i<L->length;i++)printf("%5d",L->data[i]);printf("\n");
}在主函数中调用以上函数
SqList L;int E;//初始化一个空的顺序表 initlist(&L);//调用 ListInsert(SqList *L,int i,ElemType e)向空表中加入数据元素 ListInsert(&L,1,1);ListInsert(&L,2,2);ListInsert(&L,3,3);ListInsert(&L,4,4);//显示当前顺序表中的所有数据元素 printf("当前顺序表的元素\n");list(&L);//获取当前的顺序表的长度 printf("调用getlen(&L)的结果:%d\n",getlen(&L));//取顺序表中的第1个元素并输出该元素的值 printf("调用getelem(&L,1,&E)的结果:%d\n",getelem(&L,1,&E));printf("E=%d\n",E);//输出指定元素第一次出现在顺序表中的位置 printf("调用LocateElem(&L,2)的结果:%d\n",LocateElem(&L,2));//调用 ListInsert(SqList *L,int i,ElemType e)在顺序表指定位置中加入数据元素printf("调用ListInsert(&L,2,3)的结果:%d\n",ListInsert(&L,2,3));//显示当前顺序表中的所有数据元素 printf("当前顺序表的元素\n");list(&L);//删除顺序表中指定位置的元素并将输出该位置的数据元素 printf("调用ListDelete(&L,2,&E)的结果:%d\n",ListDelete(&L,2,&E));printf("E=%d\n",E);//显示当前顺序表中的所有数据元素 printf("当前顺序表的元素\n");list(&L);2.4 链表
2.4.1 单链表
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表节点，除存放元素本身的信息外，还需要存放一个指向其后续的指针。
单链表中结点类型的描述如下：
typedef struct LNode{ //定义单链表结点类型ElemType data; //数据域struct LNode *next; //指针域
}slink;2.4.2 单链表上的基本操作
头插法建立单链表-方法一
void List_HeadInsert(slink *L)
{slink *s;int n;L->next=NULL; //初始为空表scanf("%d",&n); //输入结点值while(n!=9999) //输入9999表示结束{s=(slink *)malloc(sizeof(slink));//创建新结点s->data=n;s->next=L->next;L->next=s;scanf("%d",&n);}
}
//调用该函数创建链表需在主函数中先初始化指针L，如下
int main()
{slink *L;L=(slink *)malloc(sizeof(slink)); //创建头结点List_HeadInsert(L);return 0;
}头插法建立单链表-方法二
slink * List_HeadInsert()
{slink *s,*L;int n;L=(slink *)malloc(sizeof(slink)); //创建头结点L->next=NULL; //初始为空表scanf("%d",&n); //输入结点值while(n!=9999) //输入9999表示结束{s=(slink *)malloc(sizeof(slink));//创建新结点s->data=n;s->next=L->next;L->next=s;scanf("%d",&n);}return L;
}
//在主函数中使用如下方式调用
int main()
{slink *L;L=List_HeadInsert();return 0;
}尾插法建立单链表
slink * List_TailInsert(slink * L)
{slink *s,*r; //r为表尾指针 int n;L=(slink *)malloc(sizeof(slink)); //创建头结点r=L;scanf("%d",&n); //输入结点值while(n!=9999) //输入9999表示结束{s=(slink *)malloc(sizeof(slink));//创建新结点s->data=n;r->next=s;r=s;scanf("%d",&n);}r->next=NULL;return L;
}
//在主函数中调用该函数的方法如下
int main()
{slink *L;L=List_TailInsert(L);return 0;
}建立单链表
slink * CresList(int n)
{slink *L,*p,*s; //p用于指向新链入结点，s用于指向新开辟结点 int i;p=L=(slink *)malloc(sizeof(slink)); //创建头结点for(i=1;i<=n;i++){s=(slink *)malloc(sizeof(slink));//创建新结点scanf("%d",&s->data); //输入结点值p->next=s; //将新结点连接到p所指结点的后面 p=s; //p指向新链入结点 }p->next=NULL; //尾结点指针域置为空 return L;
}
//在主函数中调用该函数的方法如下
int main()
{slink *L;L=CresList(5);return 0;
}
求表长操作
int getlen(slink *L)
{slink *p;int n;p=L->next;n=0;while(p!=NULL){n++;p=p->next;}return n;
}取元素操作
int getlem(slink *L,int i,ElemType *e)
{slink *p;int j;if(i<1) return 0; //参数i不合理，取元素失败，返回0 p=L->next;j=1;while(p!=NULL&&j<i) //从第1个结点开始查找第i个结点 {p=p->next;j++; }if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0 *e=p->data;return 1; //取元素成功，返回1
}按值查找结点
slink * GetElem(slink *L,ElemType e)
{slink *p=L->next;while(p!=NULL&&p->data!=e)p=p->next;return p;
}插入操作
int insert(slink *L,int i,ElemType e)
{slink *p,*q;int j;if(i<1) return 0; //参数i不合理，取元素失败，返回0 p=L;j=0;while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点 {p=p->next;j++; }if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0 q=(slink *)malloc(sizeof(slink));q->data=e;q->next=p->next;p->next=q; return 1;
}删除操作
int delete(slink *L,int i,ElemType *e)
{slink *p,*q;int j;if(i<1) return 0; //参数i不合理，取元素失败，返回0 p=L;j=0;while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点 {p=p->next;j++; }if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0 q=p->next; //指向第i个结点p->next=q->next; //指向被删结点的下一个结点*e=q->data; //保存被删结点的数据值free(q); //释放被删除结点占用的空间return 1;
}输出操作
void list(slink *L)
{slink *p;p=L->next;while(p!=NULL){printf("%4d",p->data);p=p->next;}printf("\n");
}2.4.3 双链表
为了能快速方便的找到任意一个结点的前驱和后继，在结点中再增设一个指针域，指向该结点的前驱结点，这样形成的链表就有两条不同方向的链，称为双向链表，简称双链表。
双链表的结点类型定义如下：
typedef struct DNode{ElemType data;struct DNode *prior;struct DNode *next;
}dlink;2.4.4 双链表上的基本操作
建立双链表
dlink * credlink(int n)
{dlink *L,*p,*s; //p用于指向新链入结点，s用于指向新开辟结点int i;p=L=(dlink *)malloc(sizeof(dlink)); //创建头结点for(i=1;i<=n;i++){s=(dlink *)malloc(sizeof(dlink)); //s指向新开辟结点scanf("%d",&s->data); //新结点数据域赋值s->prior=p;p->next=s; //将新结点连接到p指向结点的后面p=s; //p指向新链入结点}p->next=L->prior=NULL; //头结点的前驱域和尾结点的后继域置为空return L; //返回头指针
}求表长、取元素、定位操作与单链表一样，只需要将slink替换为的dlink即可。
插入操作
int insert(dlink *L,int i,ElemType e)
{dlink *p,*q;int j;if(i<1) return 0; //参数i不合理，取元素失败，返回0p=L;j=0;while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点{p=p->next;j++;}if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0q=(dlink *)malloc(sizeof(dlink));q->data=e;q->next=p->next;q->prior=p;if(p->next!=NULL)p->next->prior=q; // 若恰好在表尾插入，因为没有后继结点，则不需要这一步p->next=q;return 1;
}删除操作
int delete(dlink *L,int i,ElemType *e)
{dlink *p,*q;int j;if(i<1) return 0; //参数i不合理，取元素失败，返回0p=L;j=0;while(p!=NULL&&j<i-1) //从第1个结点开始查找第i个结点{p=p->next;j++;}if(p==NULL) return 0; //i值超过链表长度，元素失败，返回0q=p->next; //指向第i个结点p->next=q->next; //指向被删结点的下一个结点if(p->next!=NULL)q->next->prior=p;*e=q->data; //保存被删结点的数据值free(q); //释放被删除结点占用的空间return 1;
}输出操作
void list(dlink *L)
{dlink *p;p=L;while(p->next!=NULL) //正向输出链表元素值{p=p->next;printf("%4d",p->data);}printf("\n");while(p!=L) //反向输出链表元素值{printf("%4d",p->data);p=p->prior;}printf("\n");
}2.4.5 循环链表
循环单链表
循环单链表与单链表的区别在于表中最后一个结点的指针不是NULL，而是指向头结点。循环单链表的判空条件不是头结点的指针为空，而是它是否等于头指针。
循环单链表的结点类型定义和单链表是一样的，此外，在循环单链表上的基本操作和单链表是基本一致，只需要将单链表中的判定条件p->next=!NULL、p->next=NULL分别改为p->next=!L、p->next=L即可。
循环双链表
将双链表的最后一个结点的后继指针域的值由空改为指向头结点，头结点中的前驱指针域的值由空改为指向尾结点，这样的双向链表称为双向循环链表。
循环双链表的结点类型定义和双链表是一样的，此外，在循环双链表上的基本操作和双链表是基本一致，只需要将双链表中的判定条件p->next=!NULL、p->next=NULL、p->prior=NULL分别改为p->next=!L、p->next=L、L->prior=p即可。
2.4.6 静态链表
用数组描述的链表，即称为静态链表。静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标 CUR。这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
注意：静态链表在数组存储数据是从数组的第3个位置开始的，即数组下标为2存储的是链表的第一个元素的值。
静态链表结构类型的描述如下：
typedef int ElemType; //在实际中，根据需要定义所需的数据类型
#define MaxSize 50 //静态链表中的最大长度
typedef struct{ElemType data; //存储数据元素int next; //下一个元素的数组下标
}stalink[MaxSize];初始化操作
void initlist(stalink space)
{int i;for(i=0;i<MaxSize-1;i++)space[i].next=i+1;space[MaxSize-1].next=0;
}获取结点操作
int allocnode(stalink space)
{int i;i=space[0].next;if(i==0) return 0; //链表空间已空，分配空间失败space[0].next=space[i].next;return i;
}回收结点操作
void freenode(stalink space,int i)
{space[i].next=space[0].next;space[0].next=i;
}建立静态链表
int crestalink(stalink space,int n)
{int L,k,s,i;k=L=allocnode(space);for(i=1;i<=n;i++){s=allocnode(space);scanf("%d",&space[s].data);space[k].next=s;k=s;}space[k].next=0;return L;
}求表长操作
int getlen(stalink space,int head) //head为链表头结点的下标
{int i,k;k=space[head].next;i=0;while(k!=0){i++;k=space[k].next;}return i;
}取元素操作
int getlem(stalink space,int head,int i,ElemType *e)
{int j,k;if(i<1) return 0;j=0;k=head;while(k!=0&&j<i){j++;k=space[k].next;}if(k==0) return 0;*e=space[k].data;return 1;
}定位操作
int locate(stalink space,int head,ElemType e)
{int k;k=space[head].next;while(k!=0&&space[k].data!=e)k=space[k].next;return k; //k表示的是在数组的下标，若想返回的是在链表中的第几个则用k-1;
}插入操作
int insert(stalink space,int head,int i,ElemType e)
{int j,k,m;if(i<1) return 0;k=head;j=0;while(k!=0&&j<i-1){j++;k=space[k].next;}if(k==0)return 0;m=allocnode(space);if(m!=0){space[m].data=e;space[m].next=space[k].next;space[k].next=m;return 1;}else return 0;
}删除操作
int delete(stalink space,int head,int i,ElemType *e)
{int j,k,m;if(i<1) return 0;k=head;j=0;while(k!=0&&j<i-1){j++;k=space[k].next;}if(k==0) return 0;m=space[k].next;space[k].next=space[m].next;*e=space[m].data;freenode(space,m);return 1;
}输出操作
void list(stalink space,int head)
{int i;i=space[head].next;while(i!=0){printf("%4d",space[i].data);i=space[i].next;}printf("\n");
}更多推荐
数据结构简记
发布评论