顺序链表
顺序链表其实就是一个动态的数组而已。在该链表的结构体中包含链表的基地址和链表当前的长度和链表当前已分配的存储容量。
注意:顺序链表不和单链表和双链表一样，它并不是每个元素都包含在一个结点里面。它是类似于数组，有一个类似数组名的基地址和一个表示链表当前长度的变量以及一个表示当前已分配容量的变量。并且这些均属于整个链表。并不属于某个元素。
#include <iostream>
using namespace std;
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef bool Status;
#define OK true
#define ERROR false
//定义一个链表结点
typedef struct
{
int *elem; //基地址指针，可以理解为就是一个动态数组的名字而已
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
//初始化链表函数
Status InitList(SqList &L)
{
L.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));
if (!L.elem)
{
cout << "Error!" << endl;
exit(0);
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
Status ListInsert(SqList &L,int i,int e)
{
if (i<1 || i>L.length+1)
return ERROR;
if (L.length >= L.listsize)
{
int *newbase = (int *)realloc(L.elem,(L.listsize + LISTINCREAMENT)*sizeof(int));
if (!newbase)
{
cout << "Error!" << endl;
exit(0);
}
L.listsize += LISTINCREAMENT;
L.elem = newbase;
}
int *q = &(L.elem[i-1]);//获得i元素的指针
for (int *p = &(L.elem[L.length - 1]);p >= q; --p)
{
*(p+1) = *p;
}
*q = e;
++L.length;
return OK;
}
Status ListDelete(SqList &L,int i,int &e)
{
int *p = &(L.elem[i]);
e = *p;
int *q = &(L.elem[L.length]);
for (; p != q; ++p)
{
*(p - 1) = *p;
}
--L.length;
return OK;
}
int main()
{
SqList q;
InitList(q);
for (int i = 0;i < 10; i++)
{
cin >> q.elem[i];
q.length++;
}
for (i = 0;i < q.length; i++)
{
cout << q.elem[i] << " ";
}
cout << endl;
ListInsert(q,5,6);
for (int *p = q.elem;p != &(q.elem[q.length]);++p)
{
cout << *p << " ";
}
cout << endl;
int e;
ListDelete(q,5,e);
for (p = q.elem;p != &(q.elem[q.length]);++p)
{
cout << *p << " ";
}
return 0;
}