資料結構與演算法筆記第2章線性表鏈式表示-有解無憂

2.5 鏈式結構的表示和實作

頭指標，頭結點和首元結點：
頭結點的好處：①便于首元結點的處理；②便于空表和非空表的處理；
鏈式存盤的特點：①結點在存盤器中的位置是任意的，即邏輯上相鄰的資料元素在物理上不一定相鄰；②訪問時只能通過頭指標進入鏈表，并通過每個結點的指標域依次向后順序掃描其余結點，所以尋找第一個結點和最后一個結點所花費的時間不等；
帶頭結點的單鏈表

2.5.1 單鏈表的表示

單鏈表的存盤結構：

typedef struct
{
	int num;
	char name[20];
	int score;
}ElemType;
typedef struct LNode//宣告結點的型別和指向結點的指標型別
{
	ElemType data;//結點的資料域
	struct LNode* next;//結點的指標域
}LNode, * LinkList;//LinkList 為指向結構體Lnode的指標型別
/*解釋：定義了一個結構體型別 利用typedef重新起名字為Lnode 然后定義指標LinkList指向Lnode*/
/*定義結點指標p：Lnode *p; <==> LinkList P;*/

2.5.2 單鏈表的實作

[ 演算法2.6 ] 單鏈表的初始化（帶頭結點的單鏈表）

Status InitList(LinkList& L)
{
	L = (LinkList)malloc(sizeof(LNode));
	/*L=new LNode;*/
	L->next = NULL;
	return OK;
}

[ 補充演算法 1 ] 判斷鏈表是否為空

int ListEmpty(LinkList L)
{
	if (L->next)//非空
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

[ 補充演算法 2 ] 單鏈表的銷毀
[ 演算法思路 ]從頭指標開始，依次釋放所有結點；

Status DestroyList(LinkList& L)
{
	LNode* p;//LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		free(p);
	}
	return 0;
}

[ 補充演算法 3 ] 清空鏈表（鏈表仍然存在，但鏈表中無元素，成為空鏈表）
[ 演算法思路 ]依次釋放所有結點，并將頭結點的指標域設定為空；

Status ClearList(LinkList& L)
{
	LNode* p, * q;
	p = L->next;
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;//頭結點的指標域為空
	return OK;
}

[ 演算法補充 4 ] 求單鏈表的表長
[ 演算法思路 ]從首元結點開始，依次計數所有結點；

int ListLength(LinkList L)
{
	int count = 0;//鏈表長度
	LNode* p;
	p = L->next;
	while (p)
	{
		count++;
		p = p->next;
	}
	return count;
}

[ 演算法 2.7 ] 查找第 i 個元素

Status GetElem(LinkList L, int i, ElemType& e)
{
	LNode* p;
	int j = 1;
	p = L->next;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return ERROR;
	}
	e = p->data;
	return OK;
}

[ 演算法 2.8 ] 按值查找

//O(n)
LNode* LocateElem(LinkList L, ElemType e)/*回傳地址*/
{
	LNode* p;
	p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}

int LocateElem(LinkList L, ElemType e)/*回傳元素的下標*/
{
	LNode* p;
	int j = 1;
	p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
	{
		return j;
	}
	else
	{
		return 0;
	}
}

[ 演算法 2.9 ] 插入（在第 i 個結點前插入值為 e 的新結點）

Status ListInsert(LinkList& L, int i, ElemType e)
{
	LNode *s, *p;
	int j = 0;
	s->data = e;
	p = L;
	while (p && j < i-1)//尋找i-1個結點 p指向i-1結點
	{
		p = p->next;
		j++;
	}
	if (!p || j > i-1)
	{
		return ERROR;
	}
	s->next = p->next;
	p->next = s;
	return OK;
}

[ 演算法 2.10 ] 洗掉（洗掉第 i 個結點）

Status ListDelete(LinkList& L, int i,ElemType &e)
{
	LNode* p, * q;
	int j = 0;
	p = L;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return ERROR;
	}
	q = p->next;
	p->next = q->next;//修改指標
	e = q->data;
	free(q);
	return OK;
}

[ 演算法 2.11 ] 建立單鏈表—頭插法（元素插入在鏈表頭部）

/*倒位序插入n個元素的值*/
void CreateList(LinkList& L, int n)
{
	LNode* p;
	int i;
	for (i = n; i > 0; i--)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		p->next = L->next;
		L->next = p;
	}
}

[ 演算法 2.12 ] 建立單鏈表–尾插法（元素插入在鏈表尾部）

/*正位序輸入n個元素的值*/
void CreateList(LinkList& L, int n)
{
	LNode* p, *r;
	int i;
	r = L;
	for (i = n; i > 0; i--)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		p->next = NULL;
		r->next = p;
		r = p;//尾指標指向新結點
	}
}

2.5.3 回圈鏈表

回圈鏈表：是一種頭尾相接的鏈表（即：表中最后一個結點的指標域指向頭結點，整個鏈表形成一個環）；

[ 演算法 2.13 ] 回圈鏈表的建立

void CreateList(LinkList& L, int n)
{
	LNode* p, *r;
	int i;
	r = L;
	for (i = n; i > 0; i--)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d",&p->data);
		p->next = NULL;
		r->next = p;
		r = p;
	}
	r->next = L;
}

[ 演算法 2.14 ] 帶尾指標回圈鏈表的合并

LinkList Connect(LinkList Ta, LinkList Tb)//假設Ta,Tb都是非空的單回圈鏈表
{
	LNode p;
	p = (LinkList)malloc(sizeof(LNode));
	p = Ta->next;
	Ta->next = Tb->next->next;
	free(Tb->next);
	Tb->next = p;//修改指標
	return Tb;
}

線性表的鏈式表示和實作完整參考代碼

/*先看主函式了解 2021.1.17*/
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, * LinkList;
Status InitList(LinkList& L)
{
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}
/*
void CreateList(LinkList& L, int n)
{
	LNode* p;
	for (int i = n; i > 0; i--)
	{
		p = (LNode *)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		p->next = L->next;
		L->next = p;
	}
}
*/
void CreateList(LinkList& L, int n)
{
	LNode* p, * r;
	r = L;
	for (int i = n; i > 0; i--)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d", &p->data);
		p->next = NULL;
		r->next = p;
		r = p;
	}
}
int ListLength(LinkList L)
{
	int count = 0;//用于計數
	LNode* p;
	p = L->next;
	while (p)
	{
		count++;
		p = p->next;
	}
	return count;
}
Status GetElem(LinkList L, int i, ElemType& e)
{
	int j = 1;
	LNode* p;
	p = L->next;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i)
	{
		return ERROR;
	}
	e = p->data;
	return OK;
}
int LocateElem(LinkList L, ElemType e)
{
	LNode* p;
	int j = 1;
	p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
		j++;
	}
	if (p)
	{
		return j;
	}
	else
	{
		return ERROR;
	}
}
Status ListInsert(LinkList& L, int i, ElemType e)
{
	LNode* s, * p;
	s = (LinkList)malloc(sizeof(LNode));
	int j = 0;
	p = L;
	s->data = e;
	while(p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return ERROR;
	}
	s->next = p->next;
	p->next = s;
	return OK;
}
void print(LinkList L)
{
	LNode* p;
	p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
Status ListDelete(LinkList& L, int i, ElemType& e)
{
	LNode* p, * q;
	p = L;
	q = (LinkList)malloc(sizeof(LNode));
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
	{
		return ERROR;
	}
	q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return OK;
}
void ListEmpty(LinkList L)
{
	if (L->next)
	{
		printf("鏈表非空\n");
	}
	else
	{
		printf("鏈表為空\n");
	}
}
Status ClearList(LinkList& L)
{
	LNode* p, * q;
	p = L->next;
	while (p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	L->next = NULL;
	return OK;
}
Status DestroyList(LinkList& L)
{
	LNode* p;
	while (L)
	{
		p = L;
		L = L->next;
		free(p);
	}
	printf("銷毀完畢\n");
	return OK;
}
int main()
{
	int n;
	int i;
	LinkList L;
	ElemType e;
	InitList(L);/*帶頭結點的鏈表初始化*/
	printf("輸入元素的個數：");
	scanf("%d", &n);//要輸入的元素個數
	printf("輸入元素：");
	//CreateList(L, n);/*頭插法輸入元素-倒敘狀態*/
	CreateList(L, n);/*尾插法輸入元素-順序*/
	printf("單鏈表的長度：%d\n", ListLength(L));/*求單鏈表的表長*/
	printf("輸入查找的i位置：");
	scanf("%d", &i);
	GetElem(L, i, e);/*查找第i個元素*/
	printf("查找的第i個元素是：%d\n", e);
	printf("輸入要查找得值：");
	scanf("%d", &e);
	printf("查找到的元素的下標為：%d\n", LocateElem(L, e));/*按值查找*/
	printf("插入的位置：");
	scanf("%d",&i);
	printf("要插入的元素：");
	scanf("%d", &e);
	ListInsert(L, i, e);/*第i個位置之前插入元素e*/
	printf("插入元素后的鏈表：");
	print(L);//輸出鏈表
	printf("輸入洗掉元素的位置：");
	scanf("%d", &i);
	ListDelete(L, i, e);/*洗掉第i個元素*/
	printf("洗掉的元素%d\n",e);
	printf("洗掉元素后的鏈表：");
	print(L);
	ListEmpty(L);/*判斷鏈表是否為空*/
	ClearList(L);/*清空單鏈表*/
	printf("清空單鏈表后：");
	ListEmpty(L);/*判斷鏈表是否為空*/
	DestroyList(L);/*銷毀單鏈表*/
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260678.html

標籤：其他

上一篇：希爾排序--O(N^2) --- 不穩定

下一篇：方格計數（2018年藍橋杯JavaB組）

資料結構與演算法筆記第2章 線性表 鏈式表示

2.5 鏈式結構的表示和實作

2.5.1 單鏈表的表示

2.5.2 單鏈表的實作

2.5.3 回圈鏈表

線性表的鏈式表示和實作完整參考代碼

資料結構與演算法筆記第2章線性表鏈式表示