[学习笔记]数据结构_线性表_顺序表and单链表

线性表

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面上的概念。

线性表的基本操作

bool InitList(&L)//初始化表，构造一个空的线性表

int Length(L)//求表长。返回线性表L的长度，即L中数据元素的个数

int LocateElem(L,e)//按值查找操作。在表L中查找具有给定关键字值的元素

ElemType GetElem(L,i)//按位查找操作，获取表L中第i个位置的元素的值

bool ListInsert(&L,i,e)//插入操作，在表L的第i个位置上插入指定元素e

bool ListDelete(&L,i,&e)//删除操作，删除表L中的第i个位置的元素，并用e返回删除元素的值

void PrintList(L)//输出操作，按前后顺序输出线性表L的所有元素值

bool Empty(L)//判空操作，若L为空表，则返回true,否则返回false

void DestroyList(&L)//销毁操作，销毁线性表，并释放线性表L所占用的内存空间

顺序表

顺序存储结构的优点：存储密度大，每个节点只存储数据元素。

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。

顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

单链表

定义单链表结点类型

#include<stdio.h>
#define ElemType int

typedef struct LNode{//定义单链表节点类型
	ElemType data;
	struct LNode *next;	
}LNode,*LinkList;

通常用头指针来标识一个单链表，如单链表L。

头指针为NULL时表示一个空表。

此外为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。

头结点的指针域指向线性表的第一个元素结点。

引入头结点带来的优点：①链表第一个位置上的操作和其他位置上的操作一致，无需进行特殊处理。②空表和非空表的处理得到了统一。

采用头插法和尾插法建立单链表

//建立单链表
LinkList List_HeadInsert(LinkList &L){//头插法建立单链表
	LinkList s;int x;//假设单链表的元素类型都是int好了，也别搞什么ElemType了
	L=(LinkList)malloc(sizeof(LNode));//先把头结点安排上
	L->next=NULL;//不要忘记这一步，否则单链表建成后发现尾结点不是NULL
	scanf("%d",&x);
	while(x!=9999){//输入9999就是结束
		s=(LNode*)malloc(sizeof(LNode));//创建新结点
		s->data=x;
		s->next=L->next;//注意看这一步，所以才是头插嘛
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

LinkList List_TailInsert(LinkList &L){//尾插法建立单链表
	LinkList s;int x;
	L=(LinkList)malloc(sizeof(LNode));//别忘了先把头结点的空间开辟好！
	LNode *t;//t为表尾指针
	t=L;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		t->next=s;
		t=s;
		scanf("%d",&x);
	}
	t->next=NULL;//插入结束后，安排一下尾结点的指针为NULL
	return L;
}

输出测试一下

//输出单链表，测试用的
void PrintList(LinkList L){
	LNode *s;
	s=L->next;
	printf("开始输出：\n");
	while(s!=NULL){
		printf("%d ",s->data);
		s=s->next;
	}
	printf("\n**输出结束**\n");
}

 两个查找：按值查找和按序号查找结点

//按序号查找节点
LNode *GetElem(LinkList L,int i){
	if(i<1){return NULL;}//输入不合法，直接返回NULL得了
	LNode *s=L->next;//创建一个临时指针，指向第一个元素
	int j=1;
	while(j!=i){
		s=s->next;
		j++;
	}
	return s;//直接把整个LNode结点作为结果返回了
}
//按值查找表节点
LNode *LocateElem(LinkList L,ElemType e){
	LNode *s=L->next;
	while(s->data!=e&&s!=NULL){
		s=s->next;
	}
	return s;//直接把整个LNode结点作为结果返回了
}

两个操作：插入结点操作和删除结点操作

//插入节点操作
bool ListInsert(LinkList &L,int i,ElemType e){
	
	if(i==1){
		LNode *newnode=(LNode*)malloc(sizeof(LNode));
		newnode->data=e;
		newnode->next=L->next;
		L->next=newnode;
		return true;
	}//之所以专门搞个i==1的情况还是受限于GetElem不能把头结点给弄出来
	
	LNode *s=GetElem(L,i-1);//用上边的GetElem先获取第i-1个结点******这一步要注意，可以利用已有的函数
	if(s==NULL)return false;
	
	LNode *newnode=(LNode*)malloc(sizeof(LNode));//创建一个新结点并开辟空间
	newnode->data=e;
	newnode->next=s->next;
	s->next=newnode;
	return true;
}
//删除节点操作
bool ListDelete(LinkList &L,int i){
	if(i==1){
		LNode *s=L->next;
		L->next=L->next->next;
		free(s);
		return true;
	}
	LNode *s=GetElem(L,i-1);
	if(s==NULL)return false;
	LNode *temp=s->next;
	s->next=s->next->next;
	free(temp);
	return true;
}
//求表长操作
int Length(LinkList L){
	LNode *s=L->next;
	int i=0;
	while(s!=NULL){
		s=s->next;
		i++;
	}
	return i;
}