第四次直播單鏈表的頭插與尾插

使用C++ 的參考進行讀寫資料

在這里插入圖片描述

順序表的定義

順序表

1、插入和洗掉操作移動大量元素，
2、陣列的大小不好確定
3、占用一大段連續的存盤空間，造成很多碎片，

單鏈表：邏輯上相鄰的元素在物理上不相鄰

在這里插入圖片描述

LinkList 等價于 struct LNode *

頭指標：鏈表中第一個結點的存盤位置，用來標識單鏈表，
頭結點：在單鏈表第一個結點之前附加的一個結點，為了操作上的方便

順序表的增刪改查

 #include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
typedef int ElemType;
//靜態分配
typedef struct{
	ElemType data[MaxSize];
	int length;//當前順序表中有多少個元素
}SqList;
//動態分配
#define InitSize 100
typedef struct{
	ElemType *data;
	int capacity;//動態陣列的最大容量
	int length;
}SeqList;
//i代表插入的位置，從1開始，e要插入的元素
bool ListInsert(SqList &L,int i,ElemType e)
{
	if(i<1||i>L.length+1)//判斷要插入的位置是否合法
		return false;
	if(L.length>=MaxSize)//超出空間了
		return false;
	for(int j=L.length;j>=i;j--)//移動順序表中的元素
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;//陣列下標從零開始，插入第一個位置，訪問的下標為0
	L.length++;
	return true;
}
//洗掉使用元素e的參考的目的是拿出對應的值
bool ListDelete(SqList &L,int i,ElemType &e)
{
	if(i<1||i>L.length)//如果洗掉的位置是不合法
		return false;
	e=L.data[i-1];//獲取順序表中對應的元素，賦值給e
	for(int j=i;j<L.length;j++)
		L.data[j-1]=L.data[j];
	L.length--;//洗掉一個元素，順序表長度減1
	return true;
}
//查找成功，回傳位置，位置從1開始，查找失敗，回傳0
int LocateElem(SqList L,ElemType e)
{
	int i;
	for(i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;//加1就是元素在順序表中的位置
	return 0;
}
//列印順序表元素
void PrintList(SqList &L)
{
	for(int i=0;i<L.length;i++)
	{
		printf("%4d",L.data[i]);
	}
	printf("\n");
}
int main()
{
	SqList L;//順序表的名稱
	bool ret;//查看回傳值，布爾型是True,或者False
	ElemType del;//要洗掉的元素
	//首先手動在順序表中賦值
	L.data[0]=1;
	L.data[1]=2;
	L.data[2]=3;
	L.length=3;//總計三個元素
	ret=ListInsert(L,2,60);
	if(ret)
	{
		printf("插入成功\n");
		PrintList(L);
	}else{
		printf("插入失敗\n");
	}
	ret=ListDelete(L,1,del);
	if(ret)
	{
		printf("洗掉成功\n");
		printf("洗掉元素值為 %d\n",del);
		PrintList(L);
	}else{
		printf("洗掉失敗\n");
	}
	ret=LocateElem(L,60);
	if(ret)
	{
		printf("查找成功\n");
		printf("元素位置為 %d\n",ret);
	}else{
		printf("查找失敗\n");
	}
	system("pause");//停在控制臺視窗
}

頭插法

使用頭插法新建鏈表


LinkList CreatList1(LinkList &L)//list_head_insert
{
	LNode *s;int x;
	L=(LinkList)malloc(sizeof(LNode));//帶頭結點的鏈表
	L->next=NULL;//L->data里邊沒放東西
	scanf("%d",&x);//從標準輸入讀取資料
	//3 4 5 6 7 9999
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));//申請一個新空間給s，強制型別轉換
		s->data=x;//把讀取到的值，給新空間中的data成員
		s->next=L->next;//讓新結點的next指標指向鏈表的第一個元素（第一個放我們資料的元素）
		L->next=s;//讓s作為第一個元素
		scanf("%d",&x);//讀取標準輸入
	}
	return L;
}

尾插法

使用尾插法尾插法新建鏈表

LinkList CreatList2(LinkList &L)//list_tail_insert
{
	int x;
	L=(LinkList)malloc(sizeof(LNode));//帶頭節點的鏈表
	LNode* s, * r = L;//LinkList s,r=L;也可以，r代表鏈表表尾結點，指向鏈表尾部
	//3 4 5 6 7 9999
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;//讓尾部結點指向新結點
		r=s;//r指向新的表尾結點
		scanf("%d",&x);
	}
	r->next=NULL;//尾結點的next指標賦值為NULL
	return L;
}

Tips: next指標，沒有賦值為NULL造成的

單鏈表的查找

關于 q->next = p->next ; 的理解， -> 是指標訪問成員變數（地址）p->next整體訪問結構體空間里的一個成員

按序號查找

關鍵代碼如下（偽代碼）注意特殊情況（邊界值的考慮）

LNode  *p = L->next ;
int j = 1 ;
while(P&&j<i){
   p=p->next ;
   j++ ；
}
return p ;

按值查找

關鍵代碼如下（偽代碼）注意特殊情況（邊界值的考慮）

LNode  *p = L->next ;
while( P!= NULL && p->data != e){
    p=p->next ;
}
return p ;

單鏈表的操作

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;//指向下一個結點 
}LNode,*LinkList;
//頭插法新建鏈表
LinkList CreatList1(LinkList &L)//list_head_insert
{
	LNode *s;int x;
	L=(LinkList)malloc(sizeof(LNode));//帶頭結點的鏈表
	L->next=NULL;//L->data里邊沒放東西
	scanf("%d",&x);//從標準輸入讀取資料
	//3 4 5 6 7 9999
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));//申請一個新空間給s，強制型別轉換
		s->data=x;//把讀取到的值，給新空間中的data成員
		s->next=L->next;//讓新結點的next指標指向鏈表的第一個元素（第一個放我們資料的元素）
		L->next=s;//讓s作為第一個元素
		scanf("%d",&x);//讀取標準輸入
	}
	return L;
}
//尾插法新建鏈表
LinkList CreatList2(LinkList &L)//list_tail_insert
{
	int x;
	L=(LinkList)malloc(sizeof(LNode));//帶頭節點的鏈表
	LNode* s, * r = L;//LinkList s,r=L;也可以，r代表鏈表表尾結點，指向鏈表尾部
	//3 4 5 6 7 9999
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		r->next=s;//讓尾部結點指向新結點
		r=s;//r指向新的表尾結點
		scanf("%d",&x);
	}
	r->next=NULL;//尾結點的next指標賦值為NULL
	return L;
}
//按序號查找結點值
LNode *GetElem(LinkList L,int i)
{
	int j=1;
	LNode *p=L->next;
	if(i==0)
		return L;
	if(i<1)
		return NULL;
	while(p&&j<i)
	{
		p=p->next;
		j++;
	}
	return p;
}
//按值查找
LNode *LocateElem(LinkList L,ElemType e)
{
	LNode *p=L->next;
	while(p!=NULL&&p->data!=e)
		p=p->next;
	return p;
}
//新結點插入第i個位置
bool ListFrontInsert(LinkList L,int i,ElemType e)
{
	LinkList p=GetElem(L,i-1);
	if(NULL==p)
	{
		return false;
	}
	LinkList s=(LNode*)malloc(sizeof(LNode));//為新插入的結點申請空間
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
//洗掉第i個結點
bool ListDelete(LinkList L,int i)
{
	LinkList p=GetElem(L,i-1);
	if(NULL==p)
	{
		return false;
	}
	LinkList q;
	q=p->next;
	p->next=q->next;//斷鏈
	free(q);//釋放對應結點的空間
	return true;
}
//列印鏈表中每個結點的值
void PrintList(LinkList L)
{
	L=L->next;
	while(L!=NULL)//NULL是為了代表一張空的藏寶圖
	{
		printf("%3d",L->data);//列印當前結點資料
		L=L->next;//指向下一個結點
	}
	printf("\n");
}
 
//2.3 線性表的鏈式表示
int main()
{
	LinkList L;//鏈表頭，是結構體指標型別
	LinkList search;//用來存盤拿到的某一個節點
	//CreatList1(L);//輸入資料可以為3 4 5 6 7 9999,頭插法新建鏈表
	CreatList2(L);//輸入資料可以為3 4 5 6 7 9999
	PrintList(L);//鏈表列印
	//search=GetElem(L,2);
	//if(search!=NULL)
	//{
	//	printf("按序號查找成功\n");
	//	printf("%d\n",search->data);
	//}
	//search=LocateElem(L,6);//按值查詢
	//if(search!=NULL)
	//{
	//	printf("按值查找成功\n");
	//	printf("%d\n",search->data);
	//}
	//ListFrontInsert(L,2,99);//新結點插入第i個位置
	//PrintList(L);
	//ListDelete(L,4);//洗掉第4個結點
	//PrintList(L);
}

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

標籤：其他

上一篇：Python爬蟲實戰，requests模塊，Python實作抓取騰訊視頻彈幕評論

下一篇：【python資料結構】多維陣列

C語言督學營 中期筆記 (Day3~4)

文章目錄

第四次 直播 單鏈表的頭插與尾插

順序表的定義

順序表的增刪改查

頭插法

尾插法

單鏈表的查找

按序號查找

按值查找

單鏈表的操作

C語言督學營中期筆記 (Day3~4)

第四次直播單鏈表的頭插與尾插