数据结构 静态链表

做一个豁达而努力的自己。

静态链表的定义：用数组来代替指针数组元素，由data和cur组成，data为数据域，cur代替next指针存放的是下一个后继节点的下标，称cur为游标，用数组描述的链表成为静态链表。

顺序表的静态链表存储结构：

#define MAXSIZE 1000

typedef struct Node    //这里必须加结构体名称，不加的话只能在主函数声明一个结构体数组，不能在其它函数参数里声明

{

    ElemType data;

    int cur;

}StaticLinkList[MAXSIZE];    

要点：数组的第一个元素和最后一个元素作为特殊元素处理，不存放数据；我们把未使用过的元素称为备用链表；数组第一个元素的cur存放的则是备用链表第一个节点的下标，最后一个元素则存放的是第一个有数值元素的下标，相当于头结点。

静态链表的优缺点：优点是在插入和删除时，自己只需要修改游标，，，缺点是没能解决连续分配空间带来表长难确定，失去了随机存取的特性。

代码：

#include <iostream> #include <cstdlib> using namespace std; #define MAXSIZE 1000 typedef struct Node { int data; //数据域 int cur; //游标 }StaticLinkList[MAXSIZE]; //静态链表的初始化 void InitList(StaticLinkList space) { int i; for(i = 0; i < MAXSIZE - 1; i++) space[i].cur = i + 1; space[MAXSIZE - 1].cur = 0; //个人觉得这里完全可以改为1，因为创建的时候也是要改为1的，，， } //静态链表的创建 void CreateLink(StaticLinkList space) { int n, mov; mov = MAXSIZE - 1; space[mov].cur = 1; cout << "请输入元素个数:"; cin >> n; cout << "输入int型数据:" << endl; while(n--) { mov = space[mov].cur; cin >> space[mov].data; } space[0].cur = space[mov].cur; space[mov].cur = 0; } //静态链表的输出 void PutList(StaticLinkList space) { int mov; mov = MAXSIZE - 1; while(space[mov].cur) { mov = space[mov].cur; cout << space[mov].data << endl; } } //为静态链表分配备用空间 int MallocspaceList(StaticLinkList space) { int i; i = space[0].cur; if(space[0].cur) space[0].cur = space[i].cur; return i; } //静态链表的长度 int LengthList(StaticLinkList space) { int mov, i; mov = MAXSIZE - 1; i = 0; while(space[mov].cur) { mov = space[mov].cur; i++; } return i; } //静态链表的插入 bool InsertList(StaticLinkList space, int i, int e) { if(i < 1 || i > LengthList(space)) return false; int n, mov; mov = MAXSIZE - 1; n = MallocspaceList(space); if(n) { space[n].data = e; for(int j = 1; j < i; j++) mov = space[mov].cur; space[n].cur = space[mov].cur; space[mov].cur = n; } return true; } //为静态链表释放节点 void FreeList(StaticLinkList space, int n) { space[n].cur = space[0].cur; //将第一个备用节点连接到释放节点的后面 space[0].cur = n; //数组第一个元素的cur存放要释放节点的下标 } //静态链表的删除 bool DeleteList(StaticLinkList space, int i) { if(i < 1 || i > LengthList(space)) return false; int mov, n; mov = MAXSIZE - 1; for(int j = 1; j < i; j++) mov = space[mov].cur; n = space[mov].cur; //获取删除节点的下标 space[mov].cur = space[n].cur; //将要删除的节点的前一个与后一个节点连接起来 FreeList(space, n); //释放节点 return true; } //静态链表的读取 bool GetList(StaticLinkList space, int i, int &e) { if(i < 1 || i > LengthList(space)) return false; int mov; mov = MAXSIZE - 1; for(int j = 1; j <= i; j++) mov = space[mov].cur; e = space[mov].data; return true; } //菜单 void menu() { cout << "1.静态链表的初始化" <<endl; cout << "2.静态链表的创建" <<endl; cout << "3.静态链表当前的长度" <<endl; cout << "4.静态链表的读取" <<endl; cout << "5.静态链表的插入" <<endl; cout << "6.静态链表的删除" <<endl; cout << "7.静态链表的输出" <<endl; cout << "0.退出静态链表" <<endl; } int main() { StaticLinkList space; int i, e, n, num = -1; while(num) { system("cls"); menu(); cout << "请输入选项:"; cin >> num; switch(num) { case 1: InitList(space); cout << "初始化成功" << endl; break; case 2: CreateLink(space); cout << "创建成功" << endl; break; case 3: cout << "当前静态链表的长度为:" << LengthList(space) << endl; break; case 4: cout << "请输入要读取的位置:"; cin >> i; n = GetList(space, i, e); if(n == 0) cout << "读取失败" << endl; else cout << "数据为:" << e << endl; break; case 5: cout << "请输入要插入的位置:"; cin >> i; cout << "请输入要插入的int型元素:"; cin >> e; n = InsertList(space, i, e); if(n == 0) cout << "插入失败" << endl; else cout << "插入成功" << endl; break; case 6: cout << "请输入要删除的位置:"; cin >> i; n == DeleteList(space, i); if(n == 0) cout << "删除失败" << endl; else cout << "删除成功" << endl; break; case 7: cout << "数据元素:" << endl; PutList(space); case 0: break; default : cout << "没有所选项" << endl; } system("pause"); } return 0; }