前言
线性表是数据结构中比较有特色的一类算法，本文将介绍线性表子系统的写法。
软件为VS2019
本文目的：
1.掌握线性表的特点
2.掌握线性表的顺序存储结构和链式存储结构的基本运算
3.掌握线性表的基本操作
线性表子系统题目要求：
1.设计一个选择式菜单。
2.采用单链表创建线性表。
3.在线性表中实现插入、删除元素，；显示线性表中所有元素，查找元素和求线性表长的基本操作。
一、顺序存储结构
我们知道，数组最大的特点就是它可以随时随地的任意查找所需要的元素（这是由于它在物理空间的地址上是连续的，知道了一个的地址只要在地址上增加数组的类型的字节数就可以访问到下一个元素），而条件是你要给出你要的元素的下标以及确定它存在于数组之中。那么如何建立这样的一个链表呢。
1：建立一个包含数组的结构体
#pragma once #include<iostream> #include <cstdio> #include<cstdlib> typedef int Status; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 30 #define make (struct student*)malloc(sizeof(struct student)); typedef int ElemType; typedef struct { ElemType add[MAXSIZE]; //数组基地址类型 int length; //线性表长度 1,2,3... }List;
2：获得元素（从数组中获取所需元素）
由于是基于数组，因此要获取数组中的元素非常简单，我们直接输入所需元素在数组中所在的位置i，那么i-1就是这个元素对应的下标。
Status GetElem(List L, int i, ElemType *e)//获得顺序链表里第i个数据并返回 { if (i<1 || i>L.length)//元素不存在于链表中 return ERROR; else *e = L.add[i - 1]; return OK; }
3：插入元素
Status InsertElem(List *L, int i, ElemType e)//在L中的第i个位置插入新元素e { if (i > L->length + 1 || i < 1)//判断所插入的位置是否合理 { cout << "i的值不合理！" << endl; return ERROR; } if (L->length == MAXSIZE)//判断是否超出了数组容量 { cout << "数组已满！" << endl; return ERROR; } if (i <= L->length) //要在中间插入，那么移动的次数应该是length-i+1 { cout << "数据移动！" << endl; for (int k=L->length-1;k>=i-1;k--)//插入操作，从后向前遍历 L->add[k+1] = L->add[k]; //这是由于插入后数组扩容，那么需要将插入位置之后的所有元素 } //先向后移动一个位置，腾出空位给要插入的元素，从前也可以，但是需要创建临时变量 L->add[i - 1] = e; //将要插入的数据插入数据 L->length++;//数组元素增加 return OK; }
插入元素时所需移动的次数：元素个数-1+要删除元素的位置
4：删除元素
Status DelElem(List *L,int i,ElemType *e)//移动次数length-i { int k; if (L->length == 0) //链表长度为0，说明不存在元素 { cout << "链表为空！！" << endl; return ERROR; } if (i > L->length || i < 1)//要删除的位置不合理 { cout << "i的值不对 " << endl; return ERROR; } *e = L->add[i - 1]; //读取要删除的元素的值 cout <<"要删除的值是"<< * e << endl; if (i < L->length) { for (k = i; k < L->length; k++) { //删除元素是后面的元素向前移动，那么从前往后遍历可以将后面的元素一个一个的向前覆盖 L->add[k - 1] = L->add[k]; } } L->length--; //长度减一 return OK; }
删除元素要移动的次数：元素个数-要删除位置
5：清空链表
Status FreeElem(List* L)//清空线性表 { free(L); return OK; }
6：判断链表是否为空
Status EmptyElem(List L)//判断线性表是否为空 { if (&L == NULL) return TRUE ; else return FALSE; }
7：得到链表长度
int LengthElem(List L) { return L.length-1; }
8：获得某个值所在链表的位置
int LocationElem(List L, ElemType e) { int k = 0; while (k<L.length) { if (e == L.add[k]) return k+1; else k++; } cout << "没有找到！" << endl; return ERROR; }
9：二分查找
int binarySearch(List*list,int key) { int low = 0; int high = list->length; int mid; while (low <= high) { mid = (low + high) / 2; if (list->add[mid] == key) return mid; if (list->add[mid] > key) high = mid - 1; else low = mid + 1; } }
10：代码
#include<algo.h> typedef int ElemType; typedef struct { ElemType add[MAXSIZE]; //数组基地址类型 int length; //线性表长度 1,2,3...元素个数 }List; List* InitElem() { List *head; head = (List*)malloc(sizeof(List)); head->length = 0; do { cout << "输入数据" << endl; cin >> head->add[head->length]; head->length++; } while (head->length < MAXSIZE && head->add[head->length-1] != 0.0); head->add[head->length-1]=NULL; return head; } void ShowElem(List L) { int i = 0; while(1) { if (i < L.length-1) cout << L.add[i++] << endl; else break; } } Status FreeElem(List* L)//清空线性表 { free(L); return OK; } Status EmptyElem(List L)//判断线性表是否为空 { if (&L == NULL) return TRUE ; else return FALSE; } int LengthElem(List L) { return L.length-1; } int LocationElem(List L, ElemType e) { int k = 0; while (k<L.length) { if (e == L.add[k]) return k+1; else k++; } cout << "没有找到！" << endl; return ERROR; } Status GetElem(List L, int i, ElemType *e)//获得顺序链表里第i个数据并返回 { if (i<1 || i>L.length)//元素不存在于链表中 { cout << "i的值不合理！" << endl; return ERROR; } else if (L.length == 0) { cout << "链表为空！" << endl; return ERROR; } else { *e = L.add[i - 1]; //成功后e指向的地址的值就是第i个数据的值 cout << "成功！" << endl; } return OK; } Status InsertElem(List *L, int i, ElemType e)//在L中的第i个位置插入新元素e { if (i > L->length + 1 || i < 1)//判断所插入的位置是否合理 { cout << "i的值不合理！" << endl; return ERROR; } if (L->length == MAXSIZE)//判断是否超出了数组容量 { cout << "数组已满！" << endl; return ERROR; } if (i <= L->length) //要在中间插入，那么移动的次数应该是length-i+1 { cout << "数据移动！" << endl; for (int k=L->length-1;k>=i-1;k--)//插入操作，从后向前遍历 L->add[k+1] = L->add[k]; //这是由于插入后数组扩容，那么需要将插入位置之后的所有元素 } //先向后移动一个位置，腾出空位给要插入的元素，从前也可以，但是需要创建临时变量 L->add[i - 1] = e; //将要插入的数据插入数据 L->length++;//数组元素增加 return OK; } Status DelElem(List *L,int i,ElemType& e)//移动次数length-i { int k; if (L->length == 0) //链表长度为0，说明不存在元素 { cout << "链表为空！！" << endl; return ERROR; } if (i > L->length || i < 1)//要删除的位置不合理 { cout << "i的值不对 " << endl; return ERROR; } e = L->add[i - 1]; //读取要删除的元素的值 cout <<"要删除的值是"<< e << endl; if (i < L->length) { for (k = i; k < L->length; k++) { //删除元素是后面的元素向前移动，那么从前往后遍历可以将后面的元素一个一个的向前覆盖 L->add[k - 1] = L->add[k]; } } L->length--; //长度减一 return OK; } int main() { ElemType e; List* L = InitElem(); ShowElem(*L); InsertElem(L, 3, 10); ShowElem(*L); DelElem(L, 2, e); ShowElem(*L); int location=LocationElem(*L, 1); cout << location<<endl; cout << e << endl; int num = LengthElem(*L); cout << "长度" << num << endl; int empty = EmptyElem(*L); cout << empty; FreeElem(L); ShowElem(*L); }
11：缺点
由于插入删除数据的时候需要先找到数据对应的位置之后再移动数据，因此如果要删除的数据在第一个位置，那么时间复杂度为O(1)，但是如果运气不好再最后，那么时间复杂度为O(n),因此用大O表示法表示平均时间为(n-1/2),时间复杂度为O(n)
12：优点
由于链表的顺序结构导致它可以随机任意的访问任何想要访问的元素，时间复杂度为O(10，因此它在访问方面有着巨大优势。
二、链式存储结构（方法1）
链式存储结构也就是物理空间里随机开辟空间，对其赋予数据，且这个数据中的指针域包含了下一个数据在物理空间的位置。（已经在代码里将每一步的思路都解释的非常清楚了，如果不理解可以自己画图推理一个链式存储结构的存储过程）
1：创建承载数据的载体
#pragma once #include <iostream> #include <cstdio> #include<cstdlib> #include <algorithm> #include <cmath> #include<string> #define make (struct student*)malloc(sizeof(struct student)); using namespace std; /* 链表通用代码 只需要将结构体中的数据改动 以及各函数中while的判断语句改变既可实现其他所需要的效果*/ int n = 0; //定义全局变量n，用于记录目前已有的链表节点数量 typedef struct student { char name[20]; int age; struct student * next; }s; //随便定义一个结构体
2：创建链表
struct student* creat(void) { struct student* head, * p, * tail; //创建结构体类型指针 head = NULL; //头指针指向空 n = 0; //每一次都重新使得n为0，这是由于链表需要从头到尾遍历找到尾指针后才能新建节点 p = tail = (struct student*)malloc(sizeof(struct student));//使得p与tail指向同一个起点 cin >> p->age>> p->name; //输入数据 cout << endl; while (p->age != 0) //判断当前节点是否有数据，如果没有数据说明已经到了尾节点 { n++; //数量增加 if (n == 1)head = p; //程序第一次执行if操作头节点创建,创建之后要使得next指向一个新的地址p else //程序第二次执行else操作，由于第一次执行的是if操作因此此时的p是一个相对于tail来说是一个新地址， tail->next = p; //此时p！=tail，这个操作使得tail的next指向的是新开辟好的p，读取next就可以得到新地址 tail = p;//使中间节点p与尾节点指向一个地址，这样每一次有了新的地址p，tail->next=p都能指向新的地址 p = (struct student*)malloc(sizeof(struct student));//开辟新地址 cout << "建立链表，输入学生的年龄和名字：\n"; cin >> p->age >> p->name;//为新开辟的地址输入数据 } tail->next = NULL; //已经没有数据，使尾节点指向空 //tail->next = head; //将链表改为循环链表 return(head); //返回头指针供使用 }
3：显示链表数据
void print(struct student* head)//正常的打印数据函数 { int k=0; struct student* p = head; cout << "名字\t" << "年龄\t" << endl; while (k != n) //在没有输出全部数据时持续输出 { k++; cout << p->name << "\t" << p->age << "\t" << endl; p=p->next; //输出完一次数据后链表节点指向下一个地址 } }
