线性表

顺序存储的定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

C语言中一维数组的实现就是一种顺序存储结构。

/**
ADT (List)
Data
线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType.其中，除了第一个元素a1外，每个元素有且只有一个直接的前驱元素
同理，除了最后一个元素an外，每一个元素有且仅有一个直接的后继元素，数据元素之间是一对一的关系。
Operation
InitList(*L); // 初始化操作，建立一个空的线性表.
ListEmpty(L); // 若线性表为空，则返回true,否则返回false.
ClearList(*L); // 将线性表清空.
GetElem(L,i,*e); // 将线性表L中的第i个元素值返回给e.
LocateElem(L，e); // 在线性表L中查找与给定的值e相等的元素，如果查找成功则返回该元素在表中的序列号；否则返回0，表示失败.
ListInsert(*L,i,e); // 在线性表L中的第i个位置插入新元素e.
ListDelete(*L,i,*e); // 删除线性表L中第i个位置的元素，并用元素e返回其值.
ListLength(L); // 返回线性表元素的个数.
endADT
**/

下面是线性表顺序存储的结构代码：

/*方式一*/
#define MAXSIZE 10 //初始分配量
typedef int Elemtype;//这里比较灵活，一般是可以char,int,float这些原子类型的数据
typedef struct
{
Elemtype r[MAXSIZE];//最大的存储量：数据长度（数据长度），在宏定义之后一般是不变的，以非指针的形式说明
int length; //当前长度<=MAXSIZE，线性表长度是可变的，由于增删的缘故
}Sqlist;//这一种比较好理解，但是实际写代码时会遇到L.r=a(表达式必须是可修改的左值)
//报错原因由于r[MAXSIZE]中r时数组名不是指针,不可修改,是一个分配在.bss段的确定的地址

/*方式二，更加灵活，应用指针*/
#define MAXSIZE 10
typedef int ELemtype;
typedef struct
{
Elemtype *r;
int length;
int size;//没错我们可以优化结构体，将r[MAXSIZE]拆成指针和一个int的原子数据类型，初始化是会很方便
}//这是我的数据结构书上的

//当然，如果考虑到SqlistInit()这样的函数引入，利用循环结构也可以达到同样的目的，但那会更麻烦

/*
*区分数据长度和线性表长度，数据长度一般不变，线性表长度受限于实际的元素个数
*顺序存储由于对地址LOC(ai)=LOC(a0)+sizeof(Elemtype)*i，所以时间复杂度为O(1)
*具有LOC这样的特点的结构称之为随机存储结构（比如数组）
*/

顺序存储结构

错误示范：L->data在结构体中没有指针声明（采用第一种方式声明），会显示左值无法修改的提示，此处的声明方法和上述的方式一致，此时无法改地址，其他什么的譬如修改data中的内容是可以的。

注意区分：线性表的长度与数组的长度

获取元素

3.5.1 线性表获取元素

#define OK 1
#define ERROR 0
typedef int Status; // show the status of function

Status GetElem(SqList *L,int i,ElemType *e)
{
/*check the value of i */
if (i > 0 && i < L->length && L->length != 0) // ensure the Sqlist is not Null
*e = L->data[i];
return OK;
else
printf("can't find the value");
return ERROR;
}

插入元素

3.5.2 插入算法的注意事项：

• 插入位置不合适，抛出异常（异常处理）
• L->length > L->size，则需要动态的扩容或者抛出异常
• 倒序遍历后移一位
• 元素对应插入到第i个位置
• L->length += 1

#define OK 1
#define ERROR 0
typedef int Status; // show the status of function
Status InsertElem(Sqlist *L,int i,Elemtype e)
{
if (i > L->length || i < 1) // ensure the index is normal
return ERROR;
else if (L->length >= L->size)// justify the room enough
return ERROR;
else
{
for(int j = L->length;j > i; j--)// move elements
L->data[j] = L->data[j-1]
L->data[i] = e; // j的作用域随着for循环结束而结束
}
}

链表

链表节点

typedef struct Node
{
Elemtype data;
struct Node * next;//下一个节点的地址
}Node;
typedef struct Node *Linklist ; //Linklist 是一种指针，指向节点类型

线性表与链表获取元素

GetElem()

//获取线性表对应位置的元素
#include"stdio.h"
#define OK 1
#define ERROR 0
#define True 1
#define Faulse 0
typedef int Status;//Status 返回函数的状态码，说明函数的执行情况
/*
*int GetElem( Sqlist * L，Elemtype e),返回位置
*获取元素的前提是线性表已经存在，习惯上由于返回位置非0，即0是元素不在线性表中
*要求1=<i<=L->length(即i有意义)，操作结果：返回对应位置的元素的值
*/
#define MAXSIZE 10 //指定数组的容量，即数据长度
typedef int Elemtype;
typedef struct
{
Elemtype * r;
int length;//说明线性表的长度
int size;
}Sqlist;

int main();
Status GetElem(Sqlist *L,int i,Elemtype *e);//返回这里做了优化处理，原来的int 成为状态码，返回值

int main()
{
Sqlist L;
int loc;
int a[MAXSIZE]={1,2,3,4,5,7,6,8,9,10};
L.r=a; //r在这里指针，可以修改
L.length=MAXSIZE;
Elemtype ch;
GetElem(&L,7,&ch);
printf("第七个元素是：%d",ch);
return 0;

}

Status GetElem(Sqlist *L,int i,Elemtype* e)
{
if(i<1||i>L->length)//比较的时候比的是实际的线性表长度
return ERROR;
else
{
*e=L->r[i-1];
return OK;

}

}//单链表的读取：GetElem()
/*单链表的定位一开始是相对复杂的，有点类似树中的遍历
*操作目的：获取单链表第i个元素都数据域的值
* L->next就是a1,以此类推，须注意的是循环条件
* 涉及二级指针
*/
#include"stdio.h" //没有文件的包含报未定义标识符"NULL"的错误
#include"malloc.h"
#define MAXSIZE 10
#define OK 0
#define ERROR 1
typedef int Status;
typedef int Elemtype;
typedef struct Node
{
Elemtype r;
struct Node * next;
}Node;
typedef Node * LinkList;//一级指针
int main();
Status LinkListInit(Node** L,int *a);
void GetElem(LinkList L,int i,int *e);
int main()
{ Elemtype e;
LinkList L;
int a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0};
LinkListInit(&L,a);//指针更新,这种写法没法改变L的值,可以知道L为指针，我们的目的是修改是修改指针
GetElem(L,6,&e);
printf("%d ",e);

}
Status LinkListInit(Node** L,int *a)//二级指针真香
{
Node *p;//这里使用LinkList的话报必须使用指向结构的类型

p=(Node *)malloc(sizeof(Node));//头结点申请
*L=p;//记录执行头指针的p,赋值给L;
if(!p)
return ERROR;//头结点申请失败
for(int i=0;i<=9;i++)
{
p->next=(Node *)malloc(sizeof(Node));
p->r=a[i];
p=p->next;
}
p->next=NULL;
return 0;
}

void GetElem(LinkList L,int i,int *e)
{ Node * p;
p=L;
int j=1;
while(p&&j<=i-1)
{
p=p->next;
j++;
}
*e=p->r;
}

链表插入节点

InsertElem()

/**
ADT (List)
Data
线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType.其中，除了第一个元素a1外，每个元素有且只有一个直接的前驱元素
同理，除了最后一个元素an外，每一个元素有且仅有一个直接的后继元素，数据元素之间是一对一的关系。
Operation
InitList(*L); // 初始化操作，建立一个空的线性表.
ListEmpty(L); // 若线性表为空，则返回true,否则返回false.
ClearList(*L); // 将线性表清空.
GetElem(L,i,*e); // 将线性表L中的第i个元素值返回给e.
LocateElem(L，e); // 在线性表L中查找与给定的值e相等的元素，如果查找成功则返回该元素在表中的序列号；否则返回0，表示失败.
ListInsert(*L,i,e); // 在线性表L中的第i个位置插入新元素e.
ListDelete(*L,i,*e); // 删除线性表L中第i个位置的元素，并用元素e返回其值.
ListLength(L); // 返回线性表元素的个数.
endADT
**/


/*目标：将所有的在线性表Lb中的但是不在线性表La的数据元素插入La中*/#include"stdio.h" //没有文件的包含报未定义标识符"NULL"的错误
#include"malloc.h"

#define MAXSIZE 10
#define OK 0
#define ERROR 1

typedef int Status;
typedef int Elemtype;
typedef struct Node
{
Elemtype r;
struct Node * next;
}Node;
typedef Node * LinkList;//一级指针
int main();
Status LinkListInit(Node** L,int *a);
Status ElemInsert(LinkList* L,int i,Elemtype e);
void ElemPrint(Node** L);
int main()
{ Elemtype e;
LinkList L;
int a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0};
LinkListInit(&L,a);//指针更新,可以知道L为指针,我们的目的是可以修改一级指针
ElemInsert(&L,2,11);
ElemPrint(&L);
}
Status LinkListInit(Node** L,int *a)//二级指针真香
{
Node *p;//这里使用LinkList的话必须使用指向结构的类型

p=(Node *)malloc(sizeof(Node));//头结点申请
*L=p;//记录执行头指针的p,赋值给L;
if(!p)
return ERROR;//头结点申请失败
for(int i=0;i<=9;i++)
{
p->next=(Node *)malloc(sizeof(Node));
p->next->r=a[i];
p=p->next;
}
p->next=NULL;
return 0;
}

// if have head Node

Status ElemInsert(Node**L,int i,Elemtype e){

Node *p = *L;
int j = 1;
while(p&&j<i)
{

p = p->next; //the Node of j
++j; //j
}
if(!p || j > i)
return ERROR;
Node *new = (Node*)malloc(sizeof(Node));
new->r = e;
new->next = p->next; // j+1 = i
p->next = new;
return OK;


}
void ElemPrint(Node** L)
{
Node *p = *L;
while(p->next)
{
printf("%d ",p->next->r);
p = p->next;
}
}

Q&A:

执行while之前,申请的链表之间顺次链接,从外界传入i是2,p一开始是头结点,L是头指针

当j=2时，插入节点会被放到第二个节点后面

p->r在末节点处非法读出，报segment错误

头结点的数据域被写入的,引发异常

删除节点

Status NodeDelete(LinkList *L,int i,Elemtype *e)
{
Node *p = *L;
int j = 1;
while(p->next && j < i) //aj
{
p = p->next;
++j;
}
if(!(p->next)||j > i)
return ERROR;
Node *q = p->next;//q is the Node of i
p->next = q->next;
*e = q->r;
free(q);
return OK;
}

单链表的创建

Status LinkListInit(Node** L,int *a)//二级指针真香
{
Node *p;//这里使用LinkList的话必须使用指向结构的类型

p=(Node *)malloc(sizeof(Node));//头结点申请
*L=p;//记录执行头指针的p,赋值给L;
if(!p)
return ERROR;//头结点申请失败
for(int i=0;i<=9;i++)
{
p->next=(Node *)malloc(sizeof(Node));
p->next->r=a[i];
p=p->next;
}
p->next=NULL; // 尾指针域置空
return 0;
}

静态链表

用数组描述的链表叫做静态链表，也称为游标实现法。

#include"stdio.h"
#include"malloc.h"

#define MAXSIZE 1000
#define OK 0
#define ERROR 1

typedef int Status;

typedef int Elemtype;
typedef struct
{
Elemtype data;
int cur;
}Node,StaticLinkList[MAXSIZE];// StaticLinkList is ptr


int main();
Status InitStaticLinkList(StaticLinkList L);
Status ElemInsert(LinkList* L,int i,Elemtype e);
void ElemPrint(Node** L);

Status InitStaticLinkList(StaticLinkList L)
{
int i;
for(i=0; i<MAXSIZE-1;i++)
L[i].cur = i+1;
L[MAXSIZE-1].cur = 0 ; // like head node in LinkList
return OK;
}

静态链表的插入与删除

#include"stdio.h"

#define MAXSIZE 1000
#define OK 0
#define ERROR 1

typedef int Status;

typedef int Elemtype;
typedef struct
{
Elemtype data;
int cur;
}Component,StaticLinkList[MAXSIZE];// StaticLinkList is ptr point tp Component [MAXSIZE]

//typedef StaticLinkList SLL;
typedef Component *SSL;
int main();
int Malloc_SSL(StaticLinkList L);
void Free_SSL(StaticLinkList L,int k);
int ListLength(StaticLinkList L);
Status InitStaticLinkList(StaticLinkList L);
Status ElemInsert(StaticLinkList L,int i,Elemtype e);
Status ElemDelete(StaticLinkList L,int i);
void ElemPrint(StaticLinkList L);

int Malloc_SSL(StaticLinkList L)
{
int next = L[0].cur; // the current Null

if(L[0].cur)
L[0].cur = L[next].cur; // the next Null
return next;
}

void Free_SSL(StaticLinkList L,int k)
{

L[k].cur = L[0].cur;
L[0].cur = k; // like BIN in malloc & free
}

int ListLength(StaticLinkList L)
{ int i = 0 ;
// the last elem cur is Null
int cursor = L[MAXSIZE-1].cur;
while(cursor)
{
cursor = L[cursor].cur;
i++;
}
return i;
}

Status InitStaticLinkList(StaticLinkList L)
{
int i;
for(i=0; i<MAXSIZE-1; i++)
L[i].cur = i+1;
L[MAXSIZE-1].cur = 0 ; // like head node in LinkList
return OK;
}

Status ElemInsert(StaticLinkList L,int i,Elemtype e)
{

int j , k ,l;
k = MAXSIZE - 1;
if(i<0 ||i>ListLength(L)+1)
return ERROR;
j = Malloc_SSL(L);
if (j)
{
// trans the list until the index of i
L[j].data = e;
for(l = 1; l<=i - 1;l++)
k = L[k].cur; // update k
L[j].cur = L[k].cur;// equal to L[i-1].cur
L[k].cur = j;
return OK;
}
}


Status ElemDelete(StaticLinkList L,int i)
{
int j , k ,l;
k = MAXSIZE - 1;
if(i<0 ||i>ListLength(L)+1)
return ERROR;
// trans the list until the index of i
for(l = 1; l<=i - 1;l++)
k = L[k].cur; // update k
j = L[k].cur;
L[k].cur = L[j].cur;// equal to L[i-1].cur
Free_SSL(L,i); // in case distory the cursor
return OK;

}

void ElemPrint(StaticLinkList L)
{

int cursor = L[MAXSIZE-1].cur;
while(cursor)
{
printf("%d ",L[cursor].data);
cursor = L[cursor].cur;
}

}

int main()
{
int List[6] = {1,2,3,4,5,6};
StaticLinkList InitSSL;
SSL L = InitSSL ;
InitStaticLinkList(L);
for(int i=0; i<6; i++)
ElemInsert(L,i,List[i]);
ElemPrint(L);
return 0;
}

gdb 调试的时候发现一个局部变量在Malloc_SSL函数中出错，导致没有输出。