《数据结构》第2章：线性表

您所在的位置：网站首页 › 线性表的元素类型必须是一致的吗对吗 › 《数据结构》第2章：线性表

《数据结构》第2章：线性表

2024-07-12 02:07| 来源: 网络整理| 查看: 265

第2章：线性表 2.1 线性表的定义和基本操作

线性表是具有相同数据类型的n个数据元素的有限序列。n为表长，当n=0时该线性表是一个空表。a1是唯一的『第一个』数据元素，又称表头元素。An是唯一的『最后一个』数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后驱。线性表的特点：1) 表中元素个数有限。2) 表中元素具有逻辑上的顺序性，在序列中个元素排序有其先后次序。3) 表中元素都是数据元素，每个元素都是单个元素。4) 表中的数据类型都相同。每一个元素占有相同大小的存储空间。5) 表中元素具有抽象性。即讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。线性表是一种逻辑结构，表示元素间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。线性表的基本操作：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。Destroy(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。基本操作的实现取决于采用哪一种存储结构，存储结构不同，算法的实现也不同。『&』表示C++中的引用。如果传入的变量是指针类型的变量，且在函数体内要对传入的指针进行改变，则将用到指针变量的引用。

2.2 线性表的顺序表示

线性表的顺序存储又称顺序表，是用一组地址连续的存储单元，依次存储线性表中的数据元素。顺序表的表中元素的逻辑顺序与物理顺序相同。假定线性表的元素类型为ElemType，

线性表的顺序存储类型描述为

1 #define MaxSize 50 //定义线性表的最大长度 2 typedef struct { 3 ElemType data[MaxSize]; //顺序表的元素 4 int length; //顺序表的当前长度 5 }SqList; //顺序表的类型定义

动态分配线性表

1 #define InitSize 100 //表长度的初始定义 2 typedef struct { 3 ElemType *data; //指示动态分配数组的指针 4 int MaxSize, length; //数组的最大容量和当前个数 5 } SqList;

C的初始动态分配语句为

1 L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

C++的初始动态分配语句为

1 L.data = new ElemType[InitSize];

『1』插入操作在顺序表L的第i(1= i; j++) { 8 L.data[j] = L.data[j-1]; 9 } 10 L.data[i-1] = e; 11 L.length++; 12 return true; 13 }

线性表插入算法的平均时间复杂度为O(n)。

『2』删除操作删除顺序表L中的第i(1data = x; 11 s->next = L->next; 12 L-next = s; //将新结点插入表中，L为头指针 13 scanf("d", &x); 14 } //while结束 15 return L; 16 }

采用头插法建立单链表，读入数据的顺序与生成链表中元素的顺序是相反的。每个结点插入的时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)

『2』采用尾插法建立单链表

1 LinkList CreatList2(LinkList &L) { 2 //从表头到表尾正向建立单链表L，每次均在表尾插入元素 3 int x; //设元素类型为整形 4 L = (LinkList)malloc(sizeof(LNode)); 5 LNode *s, *r = L; //r为表尾指针 6 scanf("%d", &x); //输入结点的值 7 while (x != 9999) { //输入9999表示结束 8 s = (LNode*)malloc(sizeof(LNode)); 9 s->data = x; 10 r->next = s; 11 r = s; 12 scanf("%d", &x); 13 } 14 r->next = NULL; //尾结点指针置空 15 return L; 16 }

与头插法时间复杂度相同，为O(n)

『3』按序号查找结点值在单链表中从第一个结点出发，顺指针next域诸葛往下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域NULL

1 LNode *GetElem(LinkList L, int i) { 2 //本算法取出单链表L（带头结点）中第i个位置的结点指针 3 int j = 1; //计数，初始为1 4 LNode *p = L->next //头结点指针赋给p 5 if (i == 0) 6 return L; //若i等于0，则返回头结点 7 if (i < 1) 8 return NULL; //若i无效，则返回NULL 9 while (p&&jnext; 11 j++; 12 } 13 return p; //返回第i个结点的指针，如果i大宇表长，p=NULL，直接返回p即可 14 }

『4』按值查找表结点从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该借点的指针；若整个单链表中没有这样的结点，则返回NULL。

1 LNode *LocateElem(LinkList L, ElemType e) { 2 //本算法查找单链表（带头结点）中数据域值等于e的结点操作指针，否则返回NULL 3 LNode *p = L->next; 4 while (p != NULL && p->data != e) //从第1个结点开始查找data域为e的结点 5 p = p->next; 6 return p; //找到返回该结点指针，否则返回NULl 7 }

『5』插入结点操作

插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在气候插入新结点。前插操作

1 p = GetElem（L,i-1; //查找插入位置的前驱结点 2 s->next = p->next; 3 p->next = s;

后插操作

1 s->next = p->next; //修改指针域，不能颠倒 2 p->next = s; 3 temp = p->data; //交换数据域部分 4 p->data = s->data; 5 s->data = temp;

『6』删除结点操作

1 p = GetElem(L,i-1); //查找删除位置的前驱结点 2 q = p->next; //令q指向被删除结点 3 p->next = q->next; //将*q结点从链中『断开』 4 free(q); //释放结点的存储空间

删除结点*p删除结点*p的操作可以用删除结点*p的后继结点操作来实现，实质是将其后继结点的值赋予其自身，然后删除后继结点，也能使得时间复杂度为O(1)

1 q=p->next; 2 p->data=p->next->data; 3 p->next=q->next; 4 free(q);

双链表：为克服单链表的访问某结点的前驱结点的时间复杂度为O(n)的缺点引入双链表，双链表结点中有两个指针prior和next，分别指向某前驱结点和后继结点。双链表中结点类型的描述如下：

1 typedef struct DNode { //定义双链表结点类型 2 ElemType data; //数据域 3 struct DNode *prior, *next; //前驱和后继指针 4 }DNode, *DLinklist;

『1』双链表的插入操作

在双链表中p所指的结点之后插入结点*s

1 s->next=p->next; //将结点*s插入到结点*p之后 2 p->next->prior=s; 3 s->prior=p; 4 p->next=s;

『2』双链表的删除操作

1 p->next=q->next; 2 q->next->prior=p; 3 free(q);

循环链表：循环链表和单链表的区别在于表中最后一个结点的指针不是NULL，而改为指向头结点从而整个链表形成一个环。循环单链表的判断条件不是头结点的指针是否为空，而是它是否等于头指针。循环双链表：在循环双链表中，头结点的prior指针指向表尾结点。静态链表：静态链表接住数组来描述线性表的链式存储结构。指针域next是结点的相对地址（数组下标），又称游标。静态链表结构类型的描述如下：

1 #define MaxSize 50 //静态链表的最大长度 2 typedef struct { //静态链表结构类型的定义 3 ElemType data; //存储数据元素 4 int next; //下一个元素的数组下标 5 } SLinkList[MaxSize];

顺序表和链表的比较：1) 存取方式不同。顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。2) 逻辑结构与物理结构：采用顺序存储时，逻辑上相邻的元素，其对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素其物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。3) 查找、插入和删除操作：对于按值查找，当顺序表在无序的情况下，两者的时间复杂度均为O(n)；当顺序表有序时采用折半查找，时间复杂度为O(logN)。对于按序号查找，顺序表只吃随机访问，时间复杂度仅为O(1)，而链表的平均时间复杂度为O（n）。顺序表的插入、删除操作，平均需要移动半个表厂的元素。链表的插入、删除操作，只需要修改相关结点的指针域即可。由于链表每个节点带有指针域，因而在存储空间上比顺序存储要付出较大的代价，存储密度不够大。4) 空间分配：顺序存储在静态存储器分配情形下，一旦存储空间装满就不能扩充。动态存储分配虽然可以扩充，但需要移动大量元素，导致操作效率降低。链式存储的借点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。在实际中应怎样选取存储结构？1) 基于存储的考虑：对线性表的长度或存储规模难以估计时，不宜采用顺序表。链表不用实现估计存储规模，但链表的存储密度较低。2) 基于运算的考虑：若经常按序号访问数据元素，则顺序表优于链表。插入、删除操作时链表优于顺序表。（基于时间复杂度）3) 基于环境的考虑：顺序表容易实现，链表的操作基于指针。顺序表实现较为简单。

【本文地址】

《数据结构》第2章：线性表

《数据结构》第2章：线性表

今日新闻

推荐新闻