单链表的基本操作
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的表尾
- 依次取出Lb的元素并在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;}
}
实战：图书管理系统
略
代码
顺序存储结构
//线性表--顺序存储结构
#include<iostream>
using namespace std;
template<typename T> //typename可以用class代替
struct sequentaillist {T* element;int size; //大小int capital; //容量
};template<typename T>
void initlist(sequentaillist<T>* List,int capital) { //初始化的过程其实就是分别初始化list三个变量List->element = new T[capital]; //动态分配内存 List->size = 0;List->capital = capital;
}template<typename T>
void destroylist(sequentaillist<T>* list) { //销毁线性表delete[] list->element; //释放内存
}template<typename T>
bool isempty(sequentaillist<T> list) {return list->size == 0; //判断是否为空表
}template<typename T>
int getsize(sequentaillist<T> list) { //返回表长return list.size;
}template<typename T>
void clearlist(sequentaillist<T>* list) { //清空表长，就像未使用过一样if (list == nullptr) return;delete[] list->element;list->element = nullptr;list->size = 0;list->capital = 0;
}template<typename T>
T getvalue(sequentaillist<T> list , int i) { //获取表中第i个元素的值if (list.element == nullptr) return nullptr;if (i<0 || i>list.size) {cout << "下标越界" << endl;return nullptr;}return list.element[i];
}template<typename T>
int findelement(sequentaillist<T> list, int value) { //查找元素if (list.element == nullptr) return -1;for (int i = 0; i < list.size; i++) {if (list.element[i] == value) {return i;}}return -1; //没找到
}template<typename T>
void insert(sequentaillist<T>* list, int i , T value) { //在第i个位置插入元素valueif (list == nullptr) return;if (i<0 || i>list->size) {cout << "下标越界" << endl;return;}if (list->size == list->capital) { //满了，扩容T* newelement = new T[list->capital * 2]; //扩容两倍for (int i = 0; i < list->size; i++) {newelement[i] = list->element[i];}delete[] list->element;list->element = newelement;list->capital = list->capital * 2;}for (int j = list->size; j > i; j--) {list->element[j + 1] = list->element[i];}list->element[i] = value;list->size++;
}template<typename T>
void deleteelement(sequentaillist<T>* list, int i) { //删除第i个元素if (list == nullptr) return;if (i<0 || i>list->size) {cout << "下标越界" << endl;return;}for (int j = i; j < list->size - 1; j++) {list->element[j] = list->element[j + 1];}list->size--;
}
template<typename T>
void remove(sequentaillist<T>* list, int value) { //删除表中的所有valueif (list == nullptr) return;for (int i = 0; i < list->size; i++) {if (list->element[i] == value) {deleteelement(list, i); i--; //删除位置后因为所有元素都要向前一位，覆盖了原本的i号位置，所以i号位置重新比较一遍}}
}template<typename T>
void setvalue(sequentaillist<T>* list, int i, int value) { //设置第i个元素的值if (list == nullptr) return;if (i<0 || i>list->size) {cout << "下标越界" << endl;return;}list->element[i] = value;
}
int main() {// 初始化线性表sequentaillist<int> list;initlist(&list, 5); // 初始容量为5cout << "初始化线性表，容量为5" << endl;// 插入元素insert(&list, 0, 10);insert(&list, 1, 20);insert(&list, 2, 30);cout << "插入元素后，线性表内容为：";for (int i = 0; i < list.size; i++) {cout << list.element[i] << " ";}cout << endl;// 查找元素int value = 20;int index = findelement(list, value);if (index != -1) {cout << "查找元素" << value << "，位置为：" << index << endl;}else {cout << "查找元素" << value << "，未找到" << endl;}// 删除元素deleteelement(&list, 1);cout << "删除第1个元素后，线性表内容为：";for (int i = 0; i < list.size; i++) {cout << list.element[i] << " ";}cout << endl;// 删除所有指定值的元素remove(&list, 30);cout << "删除所有值为30的元素后，线性表内容为：";for (int i = 0; i < list.size; i++) {cout << list.element[i] << " ";}cout << endl;// 设置元素值setvalue(&list, 0, 100);cout << "设置第0个元素值为100后，线性表内容为：";for (int i = 0; i < list.size; i++) {cout << list.element[i] << " ";}cout << endl;// 清空线性表clearlist(&list);cout << "清空线性表后，线性表大小为：" << getsize(list) << endl;// 销毁线性表destroylist(&list);cout << "销毁线性表" << endl;return 0;
}
链式存储结构
#include <iostream>
using namespace std;// 定义链表节点模板结构
template <typename T>
struct Node {T data; // 数据域Node<T>* next; // 指向下一个节点的指针
};// 定义链表模板类
template <typename T>
class LinkedList {
private:Node<T>* head; // 头节点指针public:// 构造函数LinkedList() : head(nullptr) {}// 析构函数~LinkedList() {destroy(head); // 销毁链表}// 初始化链表void init() {head = new Node<T>; // 创建头节点head->next = nullptr;}// 判断链表是否为空bool isempty() const {return head->next == nullptr;}// 获取链表长度int getsize() const {int count = 0;Node<T>* current = head->next;while (current) {count++;current = current->next;}return count;}// 清空链表void clear() {destroy(head->next); // 销毁链表中的所有节点head->next = nullptr; // 重置头节点的next指针}// 插入元素bool insert(int index, const T& value) {if (index < 0) return false; // 索引不能为负Node<T>* current = head;int currentIndex = 0;// 找到插入位置的前一个节点while (current != nullptr && currentIndex < index) {current = current->next;currentIndex++;}if (current == nullptr) return false; // 索引超出链表范围// 创建新节点Node<T>* newNode = new Node<T>;newNode->data = value;newNode->next = current->next;current->next = newNode;return true;}// 删除元素bool remove(int index) {if (index < 0) return false; // 索引不能为负Node<T>* current = head;int currentIndex = 0;// 找到删除位置的前一个节点while (current->next != nullptr && currentIndex < index) {current = current->next;currentIndex++;}if (current->next == nullptr) return false; // 索引超出链表范围// 删除节点Node<T>* temp = current->next;current->next = temp->next;delete temp;return true;}// 查找元素int find(const T& value) const {Node<T>* current = head->next;int index = 0;while (current != nullptr) {if (current->data == value) {return index;}current = current->next;index++;}return -1; // 未找到}// 获取指定位置的元素bool getvalue(int index, T& value) const {if (index < 0) return false; // 索引不能为负Node<T>* current = head->next;int currentIndex = 0;while (current != nullptr && currentIndex < index) {current = current->next;currentIndex++;}if (current == nullptr) return false; // 索引超出链表范围value = current->data;return true;}// 设置指定位置的元素bool setvalue(int index, const T& value) {if (index < 0) return false; // 索引不能为负Node<T>* current = head->next;int currentIndex = 0;while (current != nullptr && currentIndex < index) {current = current->next;currentIndex++;}if (current == nullptr) return false; // 索引超出链表范围current->data = value;return true;}// 销毁链表void destroy(Node<T>*& head) {Node<T>* temp;while (head) {temp = head;head = head->next;delete temp;}}// 打印链表void print() const {Node<T>* current = head->next;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}//创建链表（头插法）void creatLnode_1(int n) {head = new Node<T>; // 创建头节点head->next = nullptr;Node<T>* p;for (int i = 0; i < n; i++) {p = new Node<T>; // 创建新节点cin >> p->data; // 从标准输入读取数据p->next = head->next; // 新节点指向头节点的下一个节点head->next = p; // 头节点指向新节点}}// 创建链表（尾插法）void creatLnode_2(int n) {head = new Node<T>; // 创建头节点head->next = nullptr;Node<T>* p, * r;r = head;for (int i = 0; i < n; i++) {p = new Node<T>; // 创建新节点cin >> p->data; // 从标准输入读取数据p->next = nullptr;r->next = p; // 将新节点链接到链表末尾r = p; // 更新尾指针}}};int main() {LinkedList<int> list;// 测试头插法创建链表cout << "使用头插法创建链表：" << endl;int n1;cout << "请输入链表的长度：";cin >> n1;list.creatLnode_1(n1);cout << "链表内容：";list.print();// 测试尾插法创建链表cout << "\n使用尾插法创建链表：" << endl;int n2;cout << "请输入链表的长度：";cin >> n2;list.clear(); // 清空链表list.creatLnode_2(n2);cout << "链表内容：";list.print();// 测试插入元素cout << "\n插入元素：" << endl;int index, value;cout << "请输入插入位置和值：";cin >> index >> value;if (list.insert(index, value)) {cout << "插入成功" << endl;}else {cout << "插入失败" << endl;}cout << "链表内容：";list.print();// 测试删除元素cout << "\n删除元素：" << endl;cout << "请输入删除位置：";cin >> index;if (list.remove(index)) {cout << "删除成功" << endl;}else {cout << "删除失败" << endl;}cout << "链表内容：";list.print();// 测试查找元素cout << "\n查找元素：" << endl;cout << "请输入要查找的值：";cin >> value;int foundIndex = list.find(value);if (foundIndex != -1) {cout << "元素" << value << "的位置为：" << foundIndex << endl;}else {cout << "元素" << value << "未找到" << endl;}// 测试获取指定位置的元素cout << "\n获取指定位置的元素：" << endl;cout << "请输入要获取的元素索引：";cin >> index;int retrievedValue;if (list.getvalue(index, retrievedValue)) {cout << "第" << index << "个元素的值为：" << retrievedValue << endl;}else {cout << "索引超出范围" << endl;}// 测试设置指定位置的元素cout << "\n设置指定位置的元素：" << endl;cout << "请输入要设置的元素索引和新值：";cin >> index >> value;if (list.setvalue(index, value)) {cout << "设置成功" << endl;}else {cout << "设置失败" << endl;}cout << "\n清空链表：" << endl;list.clear();cout << "清空链表后，链表是否为空：" << (list.isempty() ? "是" : "否") << endl;return 0;
}