《[信息与通信]《数据结构》C语言版第二章_线性表》由会员分享，可在线阅读，更多相关《[信息与通信]《数据结构》C语言版第二章_线性表（87页珍藏版）》请在金锄头文库上搜索。
1、2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加第二章第二章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现1线性结构的基本特征:线性结构是一个数据元素的有序（次序）集 。1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个 “最后元素” ；3除最后元素在外，均有 唯一的后继；4除第一元素之外，均有 唯一的前驱。 2.1 2.1 线性表的类型定义线性表的类型定义2 线性表：n个数据元素组成的有限序列。 表示为（a1，a2，ai，ai+1，
2、an) 例：英文字母表（A,B,C,Z)是一个线性表例： 数据元素3 线性表的长度：表中元素的个数 n(n=0)，n=0 空表。 位序：元素ai在表中的位置数i 。 逻辑特征： v1|ai-1 ,aiD, i=2,.,n 5基本操作：结构初始化操作结构销毁操作引用型操作加工型操作 ADT List6InitList( 2. 依值在线性表LA中进行查访; 3. 若不存在，则插入之。GetElem(LB, i, / 取Lb中第i个数据元素赋给eif ( ! LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e);/ La中不存在和 e 相同的
3、数据元素，则插入之void union(List / 求线性表的长度Lb_len = ListLength(Lb); for (i = 1; i , 表的长度增加插入操作ListInsert_Sq( / q 指示插入位置for (p = p = q; -p) *(p+1) = *p;for( j=n-1; j=i-1; -j)L.elemj+1= L.elemj; L.elemj+1=e;35Status ListInsert_Sq(SqList -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK;
4、算法时间复杂度为: O( ListLength(L) )36if (L.length = L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *) realloc (L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量 if (i L.length+1) return ERROR; / 插入位置不合法37(
5、a1, , ai-1, ai, ai+1, , an) 改变为(a1, , ai-1, ai+1, , an)ai+1 an, 表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 删除操作ListDelete( e=*p; q = L.elem+L.length-1; for (+p; p L.length) return ERROR; /删除位置不合法40编写一个程序，动态地创建一个顺序表。要求：顺序表初始长度为10， 向顺序表中输入15个整数，并打印出来；在删除顺序表中的第5个元素， 打印出删除后的结果。41#include “stdio.h“ #include “
6、conio.h“ #define MaxSize 10 typedef int ElemType ; /*将int定义为ElemType*/typedef struct int *elem; int length; int listsize; Sqlist;/* 初始化一个顺序表 */ /* 参数L：Sqlist类型的指针 */ void initSqlist(Sqlist *L)L-elem=(int *)malloc(MaxSize*sizeof(ElemType);if(!L-elem) exit(0);L-length=0;L-listsize= MaxSize; /* 向顺序表中插入
7、元素 */ /* 参数L：Sqlist类型的指针 */ /* 参数i：插入元素的位置 */ /* 参数item：插入的元素 */ void InsertElem(Sqlist *L,int i,ElemType item)/*向顺序表L中第i个位置上插入元素item*/ElemType *base,* insertPtr,*p;if(iL-length+1) exit(0);if(L-length=L-listsize)base=(ElemType*)realloc(L-elem,(L-listsize+10)*sizeof(ElemType);L-elem=base;L-listsize=L
8、-listsize+100;insertPtr=for(p=p= insertPtr;p-)*(p+1)=*p;* insertPtr=item;L-length+; /* 从顺序表中删除元素 */ /* 参数L：Sqlist类型的指针 */ /* 参数i：删除元素的位置 */ void DelElem(Sqlist *L,int i) /*从顺序表L中删除第i个元素*/ElemType *delItem, *q; if(iL-length) exit(0);delItem=q=L-elem+L-length-1 ;for(+delItem; delItemlength-; /* 测试函数 *
9、/main() Sqlist l;int i;initSqlist( /*初始化一个顺序表*/for(i=0;idata表示p指向结点的数据域 (*p).nextp-next表示p指向结点的指针域二、结点和单链表的 C 语言描述aiai+1pp-nextLinkList L； / L 为单链表的头指针48三、单链表操作的实现GetElem(L, i, e) / 取第i个数据元素ListInsert( j = 1; / p指向第一个结点，j为计数器 while (p +j; / 顺指针向后查找，直到 p 指向第 i 个元素/ 或 p 为空if ( !p | ji )return ERROR; /
10、 第 i 个元素不存在 e = p-data; / 取得第 i 个元素 return OK;52ai-1 线性表的操作ListInsert( j = 0; while (p +j; / 寻找第 i-1 个结点 if (!p | j i-1)return ERROR; / i 大于表长或者小于1 55s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;eai-1aiai-1sp56 线性表的操作ListDelete ( p-next = q-
11、next; e = q-data; free(q);pq58Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next +j; / 寻找第 i 个结点，并令 p 指向其前趋 if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;59 操作 ClearList( L-next=p-next; / ClearListfree(p);算法时间复杂
12、度：O(ListLength(L)60如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程 是一个结点“逐个插入” 的过程。61例如：逆位序输入 n 个数据元素的值，建立带头结点的单链表。操作步骤： 一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；anan an-1四、依次类推，直至输入a1为止。62void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (LinkList) malloc (size
13、of (LNode);scanf( / 输入元素值p-next = L-next; L-next = p; / 插入 63补充作业：写出按正位序建立一个单链表的 算法。64回顾 2.1 节中两个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？65void union(List Lb_len =ListLength(Lb); for (i = 1; i data=e;p-next=NULL;if(!list)list=p;elser-next=p;r=p;return list; void insertList(LinkList *list,LinkLi
14、st q,ElemType e)LinkList p;p=( LinkList)malloc(sizeof(LNode);p-data=e;if(!*list)*list=p;p-next=NULL;elsep-next=q-next;q-next=p; void delLink(LinkList *list ,LinkList q)LinkList r;if(q=list)*list=q-next;free(q);elsefor(r=*list;r-next!=q;r=r-next);if(r-next!=NULL)r-next=q-next;free(q); void destroyLinkList(LinkList *list)LinkList p,q;p=*list; while(p)q=p-next;free(p);p=q;*list=NULL; 70main() int e,i;LinkList l,q;q=l=GreatLinkList(1); /*创建一个链表结点，q和l指向该结点*/scanf(“%d“,while(e) /*循环地输入数据，同时插入新生成的结点*/insertList(q=q-next;scanf(“%d“,q=l;printf(“The content of the linklistn“);while(q
