当前位置：首页 > news >正文

数据结构--线性表

news 来源：原创 2025/9/12 19:40:57

单链表的基本操作

1.清空单链表

链表仍然存在，但链表中无元素，成为空链表（头指针和头链表仍存在）
算法思路：依次释放所有结点，并将头结点指针设置为空

2.返回表长

3.取值–取单链表中第i个元素

因为存储方式为顺序存储，所以需要依次扫描

4.按值查找

返回该元素所在的位置
返回该元素对应的下标索引

5.插入结点

算法分析：

先找到第i个元素位置
将i-1元素的指针指向新节点
新节点的指针域指向原先第i个
结点数量自增1

不能直接更换2-3步的顺序，否则会导致第i个元素的位置丢失

6.删除第i个结点

7.查找、插a入和删除的时间复杂度分析

查找：
- 因为线性来拿吧只能顺序存取，即在查找时要从头指针找起，所以时间复杂度为O(n)
插入和删除
- 因线性链表不需要移动元素，只要修改指针，所以一般时间复杂度为O(n)

8.头插法建立单链表

算法分析：

从一个空表开始，重复读入数据
生成新结点，将数据存入新结点的数据域中
从最后一个结点开始依次将各节点插入链表前端

在这里插入图片描述

时间复杂度O(n)

9.尾插法创建单链表

从一个空表开始，将新结点诸葛插入链表尾部，尾指针r指向链表的尾结点
初始时r均指向头结点，每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点

代码

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
struct Lnode {													//链表结点的类型定义char name[10];int score;struct Lnode* next;
};
int init_Lnode(Lnode* L);										//单链表的初始化
int isLnode(Lnode* L);											//判断是否为空,0表示空，1表示非空
int destroyLnode(Lnode* L);										//销毁单链表
int deleteLnode(Lnode* L);										//清空单链表
int lengthLnode(Lnode* L);										//求表长
int getLnode(Lnode* L, int i, Lnode& e);						//取值，求第i个元素
Lnode* findLnode(Lnode* L, int i, char* name1, int score);		//按照值查找,返回第一个元素的位置
int insertLnode(Lnode* L, char* name2, int score);				//在第i个位置前增添一个
int denLnode(Lnode* L, int n);									//删除第n个元素的结点
void creatLnode_1(Lnode* L, int n);								//利用头插法创建链表
void creatLnode_2(Lnode* L, int n);								//利用尾插法创建链表
int main() {}
int init_Lode(Lnode *L) {L = (Lnode*)malloc(sizeof(Lnode));if (!L)	return 0;L->next = NULL;return 1;
}
int isLnode(Lnode* L) {if (!L->next)	return 0;return 1;
}
int destroyLonde(Lnode* L) {Lnode* p;while (L->next) {p = L;L = L->next;free(p);}return 1;
}
int deleteLnode(Lnode* L) {Lnode* p = L->next;Lnode* q;while (p) {q = p->next;free(p);p = q;}L->next = NULL;return 1;
}
int lengthLnode(Lnode* L) {int sum = 0;if (!isLnode(L))	return sum;Lnode* p = L->next;while (p) {sum++;p = p->next;}free(p);return sum;
}
int getLnode(Lnode* L, int i, Lnode& e) {Lnode *p = L->next;int j = 1;while (p && j < i) {p = p->next;j++;}if (!p || j>i)	return 0;e = *p;return 1;
}
Lnode* findLnode(Lnode* L, int i, char* name1, int score) {Lnode* p = L->next;while (p) {if (strcmp(p->name, name1) && p->score == score) {break;}p = p->next;}return p;
}int insertLnode(Lnode* L, char* name2, int score, int n) {int i = 0;Lnode* p = L;if (n<1 || n>lengthLnode(L) + 1) {printf("error");return 0;}while (i < n) {p = p->next;i++;}Lnode* s = (Lnode*)malloc(sizeof(Lnode));strcpy_s(s->name, name2);s->score = score;s->next = p->next;p->next = s;return 1;
}
int denLnode(Lnode* L, int n) {int i = 0;Lnode* p = L;if (n<1 || n>lengthLnode(L)) {printf("error");return 0;}while (i < n-1) {p = p->next;i++;}Lnode* s = p->next;p->next = p->next->next;free(s);return 1;
}
void creatLnode_1(Lnode* L, int n) {L = (Lnode*)malloc(sizeof(Lnode));L->next = NULL;Lnode* p;for (int i = 0; i < n; i++) {p= (Lnode*)malloc(sizeof(Lnode));scanf_s("输入姓名:%d", &p->name);scanf_s("输入成绩:%d", &p->score);p->next = L->next;L->next = p;}
}
void creatLnode_2(Lnode* L, int n) {L = (Lnode*)malloc(sizeof(Lnode));L->next = NULL;Lnode* p, * r;r = L;for (int i = 0; i < n; i++) {p = (Lnode*)malloc(sizeof(Lnode));scanf_s("输入姓名:%d", &p->name);scanf_s("输入成绩:%d", &p->score);p->next = NULL;r->next = p;r = p;		}
}

循环链表

即头尾相接的一个链表，表中最后一个结点的指针域指向头结点，使整个链表闭合成为一个环
优点：从表中任意结点出发均可找到表中其他结点
注意：循环链表中没有NULL,所以遍历时终止条件为是否等于头指针
空表：头指针指向自己
在循环链表中操作首尾元素时用的最多的是尾指针，因为头指针要找最后一个元素比较麻烦，时间复杂度高

两个循环链表的合并

操作步骤：
- p存表头结点
- Tb表头连接到Ta表尾
- 释放Tb表头结点
- Tb表尾指向Ta表头
伪代码如下：

LinkList Connect(LinkList Ta, LinkList Tb) {		//Ta和Tb均为尾指针p = Ta->next;									Ta->next = Tb->next->next;free(Tb->next);Tb->next = p;return Tb;
}

双向链表

前面链表如果需要找到某一个元素的前驱结点比较麻烦，但如果我们采用双向链表就比较方便，时间复杂度O(n)->O(1)

结构体定义伪代码如下：

typedef struct DulNode {Elemtype data;struct Dulnode* prior, * next;
};

空表：前驱后继均为NULL
对称性：
- p->next->prior = p = p->prior->next;
在双向链表中有些操作如（Listlength）等只涉及以后方向的指针，所以算法鱼线性链表相同。
但在插入删除时，许哟啊同时修改两个方向的指针，两者的时间复杂度为O(n)

双向循环链表：

头结点的前驱指针指向链表的最后一个结点
最后一个结点的后继指针指向头结点

双向链表的插入

算法分析：

s->prior = p->prior
p->prior->next = s
s->next = p
p->prior = s

伪代码如下：

int Listinsert_dul(LinkList& L, int i, Elemtype e) {		//Elemtype为题目所需压要的数据类型if (!(p = GetElem_dul(L, i)))		return 0;			//将p指向第i个元素s = new DulLnode;	s->data = e;s->prior = p->prior;p->prior->next = s;s->next = p;p->prior = s;return 1;
}

双向链表的删除

算法分析：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

p->prior->next = p->next;
p->next->prior = p->prior

伪代码如下：

int Listinsert_dul(LinkList& L, int i, Elemtype &e) {		//Elemtype为题目所需压要的数据类型if (!(p = GetElem_dul(L, i)))		return 0;			//将p指向第i个元素e = p->data;p->prior->next = p->next->prior;p->next->prior = p->prior->next;free(p);return 1;
}

如果知道要删除的位置，那么时间复杂度为O(1)，但为了查找第i个元素的位置所以总的时间复杂度为O(n)

单链表、循环链表和双向链表的时间效率比较

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

顺序表和链表的比较

链表的优点：

结点空间可以动态申请和释放
逻辑次序通过结点的指针表示，插入和删除时不需要移动大量的数据元素

缺点：

每个指针域需要额外的占用空间
存储密度比较小
非随机存取结构，对结点的操作都要从头指针沿着指针链查找，增加了算法的复杂度

存储密度指结点中数据本身所占系结点总空间的比重，即数据所占空间/结点总空间

一般存储密度越大，存储空间的利用率越高

线性表的合并

问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A = A∪B
- 如La = (7，5，3，11)，Lb = (2，6，3) —>La = (7，5，3，11，2，6)
- 算法分析：
  - 依次取出Lb的元素并在La中查找
    - 如果有，直接跳过该元素
    - 如果没有，则插入到La的表尾

伪代码如下：

void union(List& a, LIst b) {a_len = Listlength(a);b_len = Listlength(b);for (int i = 0; i < b_len; i++) {GetElem(b, i, e);if (!Locate(a, e)) {Listinsert(&a, ++a_len, e);				//即添加完后元素个数自增1}}
}

有序表的合并(顺序表)

已知La和Lb中的数据元素按照非递减有序排列合并为一个新的线性表Lc，且Lc中的元素也是按照值非递减有序排列

La=(1，7，8) Lb=(2，4，6，8，10，11)

–》Lc=(1，2，4，6，7，8，8，10，11)

算法步骤：

创建一个空表Lc
依次从La和Lb中摘取值较小的结点插入到Lc表的最后，直至某方变为一个空表为止
继续从另一个表中读取剩余元素

void MergeList1(List a, List b, List& c) {pa = a.elem;pb = b.elem;											//pa和pb分别指向第一个元素c.length = a.length + b.length;c.elem = new elem[c.length];pa_last = pa.elem + pa.length - 1;pb_last = pb.elem + pb.length - 1;while (pa <= pa_last && pb <= pb_last) {if (*pa <= *pb)	*pc++ = *pa++;else  *pc++ = *pb++;}while (pa <= pa_last) {*pc++ = *pa++;}while (pb <= pb_last) {*pc++ = *pb++;}
}

有序表的合并(链表)

算法步骤上同

伪代码：

void MergeList2(List a, List b, List& c) {pa = a->next;pb = b->next;pc = c = a;while (a && b) {if (a->data < b->data) {pc->next = pa;pc = pa;pa = pa->next;}else {pc->next = pb;pc = pb;pb= pb->next;}}pc->next = a ? a : b;delete(b);
}

实战：多项式相加运算

typedef struct aaa {float p;        //系数int e;          //指数
};
typedef struct bbb{aaa data;struct bbb* next;
}*List;
void add(List a, List b) {Lnode* p1 = a->next;Lnode* p2 = b->next;Lnode* pa = a;while (p1 && p2) {if (p1->data.e == p2->data.e) {p1->data.e += p2->data.e;if (p1->data.e == 0) {p1 = p1->next;p2 = p2->next;}else {pa->next = p1;pa = p1;p1 = p1->next;p2 = p2->next;continue;}}else if (p1->data.e < p2->data.e) {pa->next = p1;pa = p1; p1 = p1->next;}else {pa->next = p2;pa = p2;p2 = p2->next;}}if (p1) pa->next = p1;if (p2) pa->next = p2;
}

实战：稀疏多项式的运算

算法分析(顺序表)：

先将两个多项式转化为存储为线性表形式
创建一个新的数组
分别遍历比较两个线性表的每一项
- 指数相同，对应系数相加，若其和不为0，则在新数组中增加一个新项
- 指数不同，将指数较小的项复制到新数组中
一个多项式遍历完毕后，将另外一个剩余项依次复制进新数组即可
问题：新数组应该多大？
- 存储空间分配不灵活
- 运算空间复杂度高

线性表分析大同小异,算法分析略

结点结构体的定义:

struct polynode{int coef;int exp;polynode *next;
}polynode,polylist;

尾插法创建线性表:

polylist polycreate() {	//尾插法polynode *head,*rear,*s;int c,e;head=(polynode *)malloc(sizeof(polynode));rear=head;scanf("%d %d",&c,&e);while(c!=0){s=(polynode *)malloc(sizeof(polynode));s->coef=c;s->exp=e;rear->next=s;rear=s; scanf("%d %d",&c,&e);}rear->next=NULL;//将表的最后一个结点的next置NULL，以表示结束return (head); 
}

实现两个多项式相加：

void polyadd(polylist polya, polylist polyb){
//将两个多项式相加，然后将和多项式存放在polya中，并将polyb删除polynode* p, * q, * tail, * temp;int sum;p = polya->next;q = polyb->next;tail = polya;//tail指向和多项式的尾结点while (p != NULL && q != NULL) {if (p->exp < q->exp){tail->next = p;tail = p;p = p->next;}else if (p->exp == q->exp){sum = p->coef + q->coef;if (sum != 0)//若系数和非0，则系数和置入结点p，释放结点q，并将指针后移{p->coef = sum;tail->next = p;tail = p;p = p->next;temp = q;q = q->next;free(temp);}else {//若系数和为0.删除p，q，并将指针指向下一个结点temp = p;p = p->next;free(temp);temp = q;q = q->next;free(temp);}}else {tail->next = q;tail = q;q = q->next;}}if (p != NULL){tail->next = p;tail = p;p = p->next;}else {tail->next = q;tail = q;q = q->next;}
}

实战：图书管理系统

略
sum = p->coef + q->coef;
if (sum != 0)
//若系数和非0，则系数和置入结点p，释放结点q，并将指针后移
{
p->coef = sum;
tail->next = p;
tail = p;
p = p->next;
temp = q;
q = q->next;
free(temp);
}
else {
//若系数和为0.删除p，q，并将指针指向下一个结点
temp = p;
p = p->next;
free(temp);
temp = q;
q = q->next;
free(temp);
}
}
else {
tail->next = q;
tail = q;
q = q->next;
}
}
if (p != NULL){
tail->next = p;
tail = p;
p = p->next;
}
else {
tail->next = q;
tail = q;
q = q->next;
}
}


## 实战：图书管理系统略

单链表的基本操作

1.清空单链表

2.返回表长

3.取值–取单链表中第i个元素

4.按值查找

5.插入结点

6.删除第i个结点

7.查找、插a入和删除的时间复杂度分析

8.头插法建立单链表

9.尾插法创建单链表

代码

循环链表

两个循环链表的合并

双向链表

双向链表的插入

双向链表的删除

单链表、循环链表和双向链表的时间效率比较

顺序表和链表的比较

线性表的合并

有序表的合并(顺序表)

有序表的合并(链表)

实战：多项式相加运算

实战：稀疏多项式的运算

实战：图书管理系统

相关文章：