文章目录
线性表线性表基本操作代码实现单链表首元结点、头结点、头指针单链表基本操作代码实现单向链表课后实验题双向链表双向链表的基本操作队列线性表
什么是线性表？由n(n>=0)个数据特性相同的元素构成的有序序列称为线性表，线性表中的元素个数n定义为线性表的长度，n=0时称为空表。对于非空的线性表或线性结构
（1）存在唯一的一个被称作“第一个”的数据元素
（2）存在唯一的一个被称作“最后一个”的数据元素
（3）出第一个元素之外,结构中的每个数据元素均只有一个前驱
（4）除最后一个元素之外,结构中每个数据元素均只有一个后继
线性表基本操作代码实现
【初始化顺序表】
/*** 初始化顺序表* @param L 顺序表* @return Ok表示初始化成功*/Status InitList(NumList &L){L.elem = new int[MAXSIZE];if(!L.elem)exit(ERROR);L.length = 0;return OK;}
【顺序表的插入】
/*** 插入元素* @param i 要插入的位置* @param e 要插入的元素* @return*/Status ListInsert(NumList &L,int i,int e){if(i<1||i>L.length+1||L.length==MAXSIZE){cout<<"插入成功"<<endl;return ERROR;}for(int j=L.length-1;j>=i-1;j--){L.elem[j+1] = L.elem[j];}L.elem[i-1] = e;++L.length;cout<<"插入成功"<<endl;return OK;}
【顺序表的删除】
/*** 根据位置删除元素* @param i 要算出元素的位置* @return*/Status ListDelete(NumList &L,int i){if (i<1||i>L.length) return ERROR;for (int j=i;j<=L.length-1;j++){L.elem[j-1] = L.elem[j];}--L.length;cout<<"删除成功"<<endl;return OK;}//删除大于min小于max的元素Status DeleteByNum(NumList &L,int min,int max){for(int i=0;i<L.length;i++){if(L.elem[i]>min && L.elem[i]<max) {ListDelete(L,i+1);i--;}}return 0;}
【顺序表的查找】
/*** 根据目标元素查找顺序表* @param L* @param e 要查找的元素* @return 返回元素的位置，没找到就返回0*/int LocateElem(NumList &L,int e) {for(int i=0;i<L.length;i++){if(L.elem[i] == e) return i+1;}return 0;}
【遍历顺序表】
/*** 遍历顺序表* @param L 顺序表*/void ShowList(NumList L){if(L.length == 0){cout<<"顺序表为空"<<endl;return;}for(int i=0;i<L.length;i++){cout<<L.elem[i]<<" ";}cout<<endl;}
【头文件及主函数】
#include<iostream>#define MAXSIZE 100#define OK 1#define ERROR 0using namespace std;typedef int Status;struct NumList{int *elem;int length;};int main(){NumList L;InitList(L);//初始化顺序表for (int i = 0; i < 10; ++i) {ListInsert(L,i,i);//插入10个元素}ShowList(L);ListDelete(L,2);//删除第二个元素cout<<"删除元素后的顺序表：";ShowList(L);DeleteByNum(L,2,7);//删除大于2小于7的元素cout<<"删除大于2小于7的元素后的顺序表：";ShowList(L);return 0;}
单链表
什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表的指针链接实现的。链表当中的每一个元素称为一个结点，这些结点可以在程序运行的过程中动态的生成每一个结点分为两个区域：
data域（存放数据元素）
next域（存放的是下一个结点的地址）链表的特点：
插入或删除中间的元素是效率高，查找效率低。
首元结点、头结点、头指针
首元结点：指链表中存储第一个元素的结点 如结点“ZHAO”头节点：头结点是在首元结点之前附设一个结点，其指针域指向首元结点。头节点的数据域可以 不存储任何信息，也可以存储与数据元素类型相同的附加信息。如当数据元素为整数型时，可在头节点的数据域存放该链表的长度。头指针：头指针是指向链表中第一个结点的指针，若链表有头结点则头指针指向头结点，若链表没有头节点则头指针指向首元结点单链表基本操作代码实现
【初始化】
//初始化Status InitList(LinkList &L){L = new LNode;L->next = NULL;return OK;}
【插入结点】
/*** 按照位置插入结点* @param L 单链表* @param i 要插入结点的位置（从1开始）* @param e 要插入的结点*/Status ListInsert(LinkList &L,ElemType a,ElemType b,ElemType e){LinkList p = L;while (p && (p->data.no!=a.no&&p->data.no!=b.no)){p = p->next;if(!p->next)return ERROR;};/*插入结点*/LNode* s = new LNode;s->data = e;s->next = p->next;p->next = s;return OK;}/*** 头插法* @param L 链表* @param n 插入结点的个数*/void CreateList_H(LinkList &L,int n){L = new LNode;L->next = NULL;for (int i = 0; i < n; ++i) {LNode* p = new LNode;cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;cin>>p->data.no>>p->data.name;p->next = L->next;L->next = p;}}/*** 尾插法*/void CreateList_R(LinkList &L, int n){L = new LNode;L->next = NULL;//建立带头结点的空链表LNode *r = L;for (int i = 0; i < n; ++i) {LNode* p = new LNode;cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;cin>>p->data.no>>p->data.name;p->next = NULL;r->next = p;r = p;}}
【删除结点】
/*** 按照位置删除结点* @param L 链表* @param i 要删除结点的位置*/Status ListDelete(LinkList &L,int i){LinkList p = L;int j = 0;while (p && j<i-1){p = p->next;j++;}if(!p || j>i-1){return ERROR;}LNode *q = p->next;p->next = q->next;delete q;return OK;}
【查找结点】
/*** 查找第i个结点* @param L 链表* @param i 位置* @param e 保存当前结点的数据域*/Status GetElem(LinkList &L,int i,ElemType &e){LNode* p = L->next;int j = 1;while (p!=NULL && j<i){p = p->next;j++;}if (p==NULL && j>i){return ERROR;}e = p->data;return OK;}/*** 单链表的按学号查找* @param L 单链表* @param no 学号* @return 结点*/LNode* LocateElem(LinkList L,int no){LNode* p = L->next;while (p && p->data.no!=no){p = p->next;}return p;}
【遍历链表】
//遍历链表void Show(LinkList L){LNode* p = L->next;while (p){cout<<p->data.no<<"+"<<p->data.name<<" ";p = p->next;}return;}
【反转链表】
//反转链表Status reverse(LinkList &L){LNode* p = L->next;L->next = NULL;while (p){LNode* q = p->next;p->next = L->next;L->next = p;p=q;}return OK;}
【头文件及主函数】
#include <iostream>#include <string>#define OK 1#define ERROR 0using namespace std;typedef int Status;struct ElemType{int no;string name;};typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;int main(){ElemType e1 = {1,"张三"};ElemType e2 = {2,"李四"};ElemType e3 = {3,"王五"};LNode* L;InitList(L);CreateList_R(L,5);Show(L);cout<<"插入后"<<endl;ListInsert(L,e1,e2,e3);Show(L);cout<<"反转后"<<endl;reverse(L);Show(L);}
单向链表课后实验题
课后实验题
双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双向链表的基本操作
【双向链表的插入】
/*双向链表的插入*/Status ListInsert_Dul(DulLinkList &DL,int i,int data){DulNode* p;if(!(p=GetElem_Dul(DL,i)))return ERROR;DulNode* s = new DulNode;s->data = data;s->prior = p->prior;p->prior->next = s;s->next = p;p->prior = s;return OK;}
【双向将链表的删除】
/*双向链表的删除*/Status ListDelete_Dul(DulLinkList &DL,int i){DulNode* p;if (!(p=GetElem_Dul(DL,i)))return ERROR;p->prior->next = p->next;p->next->prior = p->prior;delete p;return OK;}
【头文件及主函数】
#include<iostream>#include <string>#define OK 1#define ERROR 0using namespace std;typedef int Status;typedef struct DulNode{int data; //数据域struct DulNode *prior; //直接前驱struct DulNode *next; //直接后继}DulNode,*DulLinkList;/*初始化*/Status InitDulList(DulLinkList &DL){DL = new DulNode;DL->prior = DL;DL->next = DL;return OK;}DulNode* GetElem_Dul(DulLinkList &DL,int i){DulNode *p = DL->next;int j = 1;while (p && j<i){p = p->next;j++;}if (!p || j>i)return NULL;return p;}/*遍历双向链表*/void Show(DulLinkList L){DulNode *p = L->next;if (p->next == p) {cout<<"NULL"<<endl;return;} //链表为空while(p->next != L->next){cout<<p->data<<" ";p = p->next;}return;}int main(){DulNode *DL;InitDulList(DL);ListInsert_Dul(DL,1,1);ListInsert_Dul(DL,1,2);ListInsert_Dul(DL,1,3);ListInsert_Dul(DL,2,4);Show(DL);ListDelete_Dul(DL,1);Show(DL);}
队列
队列
