C語言線性表全面梳理操作方法

更新時(shí)間：2022年04月22日 14:49:49 作者：平凡的人1

線性表，數(shù)據(jù)結(jié)構(gòu)中最簡單的一種存儲(chǔ)結(jié)構(gòu)，專門用于存儲(chǔ)邏輯關(guān)系為"一對一"的數(shù)據(jù)。線性表是基于數(shù)據(jù)在實(shí)際物理空間中的存儲(chǔ)狀態(tài)，又可細(xì)分為順序表（順序存儲(chǔ)結(jié)構(gòu)）和鏈表

線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列

強(qiáng)調(diào)幾點(diǎn)：

首先它是一個(gè)序列。也就是說，元素之間是有順序的，若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其他都有一個(gè)前驅(qū)和后繼。
其次線性表強(qiáng)調(diào)是有限的。

線性表有兩種物理結(jié)構(gòu)，第一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。用c語言的一維數(shù)組來實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)。

線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

可以快速地讀取表中任一位置的元素
無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間

缺點(diǎn)：

插入和刪除操作需要移動(dòng)大量元素
當(dāng)線性表長度變化較大時(shí)，難以確定存儲(chǔ)空間的容量，造成存儲(chǔ)空間的“破碎”

實(shí)際上，順序存儲(chǔ)結(jié)構(gòu)最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素，這顯然就需要耗費(fèi)時(shí)間。于是我們迎來了線性表的第二種存儲(chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。

在順序存儲(chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素之需要存儲(chǔ)數(shù)據(jù)元素信息就可以了。現(xiàn)在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存儲(chǔ)數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼元素的地址。

把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱為指針域

下面來說說鏈表的優(yōu)點(diǎn)在哪里

基于結(jié)構(gòu)體指針
可動(dòng)態(tài)地分配存儲(chǔ)
所有結(jié)點(diǎn)離散分布，僅由指針聯(lián)系起來

準(zhǔn)備工作

頭文件

#include "stdio.h"    
#include "stdlib.h"  
#include "math.h"  
#include "time.h"

宏定義以及typedef的使用

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */
typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

結(jié)構(gòu)體及其定義

typedef struct Node
{
    ElemType data;
    struct Node* next;
}Node;
typedef struct Node* LinkList; /* 定義LinkList */

malloc函數(shù)

這里簡單說一下malloc函數(shù)的用法

指針自身=（指針類型*）malloc（sizeof（指針類型））

注：

malloc返回的是無類型的指針，在使用時(shí)一定要強(qiáng)制轉(zhuǎn)換為所需類型
開辟空間后，一定要釋放空間，否則會(huì)造成內(nèi)存泄漏。
free（p）函數(shù)，釋放p所指變量的存儲(chǔ)空間，徹底刪除一個(gè)變量

其他注意事項(xiàng)

當(dāng)你傳遞一個(gè)參數(shù)給函數(shù)的時(shí)候，這個(gè)參數(shù)會(huì)不會(huì)在函數(shù)內(nèi)被改動(dòng)決定了使用什么參數(shù)形式
如果需要被改動(dòng)，則需要傳遞指向這個(gè)參數(shù)的指針
如果不需要被改動(dòng)，可以直接傳遞這個(gè)參數(shù)。

請時(shí)刻注意這點(diǎn)，不要老是遇到函數(shù)一會(huì)要指針，一會(huì)不要指針的時(shí)候一頭霧水，搞不明白。

下面說一說單鏈表基本的操作

單鏈表的初始化（頭結(jié)點(diǎn)指針域置為空）

/* 初始化鏈?zhǔn)骄€性表 */
Status InitList(LinkList* L)
{
    *L = (LinkList)malloc(sizeof(Node)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */
    if (!(*L)) /* 存儲(chǔ)分配失敗 */
        return ERROR;
    (*L)->next = NULL; /* 指針域?yàn)榭?*/
    return OK;
}

判斷鏈表是否為空（實(shí)際上就是根據(jù)頭結(jié)點(diǎn)是否為空?？辗祷?，非空返回0）

/* 初始條件：鏈?zhǔn)骄€性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */
Status ListEmpty(LinkList L)
{
    if (L->next)
        return FALSE;
    else
        return TRUE;

清空鏈表

/* 初始條件：鏈?zhǔn)骄€性表L已存在。操作結(jié)果：將L重置為空表 */
Status ClearList(LinkList *L)
{ 
	LinkList p,q;
	p=(*L)->next;           /*  p指向第一個(gè)結(jié)點(diǎn) */
	while(p)                /*  沒到表尾 */
	{
		q=p->next;
		free(p);
		p=q;
	}
	(*L)->next=NULL;        /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/
	return OK;
}

求鏈表的表長

/* 初始條件：鏈?zhǔn)骄€性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */
int ListLength(LinkList L)
{
    int i = 0;
    LinkList p = L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
    while (p)
    {
        i++;
        p = p->next;
    }
    return i;
}

取值

/* 初始條件：鏈?zhǔn)骄€性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;		/* 聲明一結(jié)點(diǎn)p */
	p = L->next;		/* 讓p指向鏈表L的第一個(gè)結(jié)點(diǎn) */
	j = 1;		/*  j為計(jì)數(shù)器 */
	while (p && j<i)  /* p不為空或者計(jì)數(shù)器j還沒有等于i時(shí)，循環(huán)繼續(xù) */
	{   
		p = p->next;  /* 讓p指向下一個(gè)結(jié)點(diǎn) */
		++j;
	}
	if ( !p || j>i ) 
		return ERROR;  /*  第i個(gè)元素不存在 */
	*e = p->data;   /*  取第i個(gè)元素的數(shù)據(jù) */
	return OK;
}

按值查找

/* 初始條件：鏈?zhǔn)骄€性表L已存在 */
/* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系的數(shù)據(jù)元素的位序。 */
/* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到這樣的數(shù)據(jù)元素 */
                return i;
        p=p->next;
    }
    return 0;
}

插入

/* 初始條件：鏈?zhǔn)骄€性表L已存在,1≤i≤ListLength(L)， */
/* 操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{ 
	int j;
	LinkList p,s;
	p = *L;   
	j = 1;
	while (p && j < i)     /* 尋找第i個(gè)結(jié)點(diǎn) */
	{
		p = p->next;
		++j;
	} 
	if (!p || j > i) 
		return ERROR;   /* 第i個(gè)元素不存在 */
	s = (LinkList)malloc(sizeof(Node));  /*  生成新結(jié)點(diǎn)(C語言標(biāo)準(zhǔn)函數(shù)) */
	s->data = e;  
	s->next = p->next;      /* 將p的后繼結(jié)點(diǎn)賦值給s的后繼  */
	p->next = s;          /* 將s賦值給p的后繼 */
	return OK;
}

刪除

/* 初始條件：鏈?zhǔn)骄€性表L已存在，1≤i≤ListLength(L) */
/* 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值，L的長度減1 */
Status ListDelete(LinkList *L,int i,ElemType *e) 
{ 
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	/* 遍歷尋找第i個(gè)元素 */
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i) 
	    return ERROR;           /* 第i個(gè)元素不存在 */
	q = p->next;
	p->next = q->next;			/* 將q的后繼賦值給p的后繼 */
	*e = q->data;               /* 將q結(jié)點(diǎn)中的數(shù)據(jù)給e */
	free(q);                    /* 讓系統(tǒng)回收此結(jié)點(diǎn)，釋放內(nèi)存 */
	return OK;
}

單鏈表的建立——頭插法

/*  隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L（頭插法） */
void CreateListHead(LinkList* L, int n)
{
    LinkList p;
    int i;
    srand(time(0));                         /* 初始化隨機(jī)數(shù)種子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;                      /*  先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */
    for (i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node)); /*  生成新結(jié)點(diǎn) */
        p->data = rand() % 100 + 1;             /*  隨機(jī)生成100以內(nèi)的數(shù)字 */
        p->next = (*L)->next;
        (*L)->next = p;						/*  插入到表頭 */
    }
}

單鏈表的建立——尾插法

/*  隨機(jī)產(chǎn)生n個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線性表L（尾插法） */
void CreateListTail(LinkList* L, int n)
{
    LinkList p, r;
    int i;
    srand(time(0));                      /* 初始化隨機(jī)數(shù)種子 */
    *L = (LinkList)malloc(sizeof(Node)); /* L為整個(gè)線性表 */
    r = *L;                                /* r為指向尾部的結(jié)點(diǎn) */
    for (i = 0; i < n; i++)
    {
        p = (Node*)malloc(sizeof(Node)); /*  生成新結(jié)點(diǎn) */
        p->data = rand() % 100 + 1;           /*  隨機(jī)生成100以內(nèi)的數(shù)字 */
        r->next = p;                        /* 將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn) */
        r = p;                            /* 將當(dāng)前的新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn) */
    }
    r->next = NULL;                       /* 表示當(dāng)前鏈表結(jié)束 */
}

注：關(guān)于p->data的數(shù)據(jù)你也可以改成手動(dòng)輸入，不必讓它隨機(jī)產(chǎn)生

重要的是能理解頭插法或者尾插法的算法思想

輸出

/* 初始條件：鏈?zhǔn)骄€性表L已存在 */
/* 操作結(jié)果：依次對L的每個(gè)數(shù)據(jù)元素輸出 */
Status ListTraverse(LinkList L)
{
    LinkList p = L->next;
    while (p)
    {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

Status visit(ElemType c)
{
    printf("%d ", c);
    return OK;
}

主函數(shù)

int main()
{
    LinkList L;
    ElemType e;
    Status i;
    int j, k;
    i = InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n", ListLength(L));
    for (j = 1; j <= 5; j++)
        i = ListInsert(&L, 1, j);
    printf("在L的表頭依次插入1～5后：L.data=");
    ListTraverse(L);
    printf("ListLength(L)=%d \n", ListLength(L));
    i = ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);
    i = ClearList(&L);
    printf("清空L后：ListLength(L)=%d\n", ListLength(L));
    i = ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n", i);
    for (j = 1; j <= 10; j++)
        ListInsert(&L, j, j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L);
    printf("ListLength(L)=%d \n", ListLength(L));
    ListInsert(&L, 1, 0);
    printf("在L的表頭插入0后：L.data=");
    ListTraverse(L);
    printf("ListLength(L)=%d \n", ListLength(L));
    GetElem(L, 5, &e);
    printf("第5個(gè)元素的值為：%d\n", e);
    for (j = 3; j <= 4; j++)
    {
        k = LocateElem(L, j);
        if (k)
            printf("第%d個(gè)元素的值為%d\n", k, j);
        else
            printf("沒有值為%d的元素\n", j);
    }
    k = ListLength(L); /* k為表長 */
    for (j = k + 1; j >= k; j--)
    {
        i = ListDelete(&L, j, &e); /* 刪除第j個(gè)數(shù)據(jù) */
        if (i == ERROR)
            printf("刪除第%d個(gè)數(shù)據(jù)失敗\n", j);
        else
            printf("刪除第%d個(gè)的元素值為：%d\n", j, e);
    }
    printf("依次輸出L的元素：");
    ListTraverse(L);
    j = 5;
    ListDelete(&L, j, &e); /* 刪除第5個(gè)數(shù)據(jù) */
    printf("刪除第%d個(gè)的元素值為：%d\n", j, e);
    printf("依次輸出L的元素：");
    ListTraverse(L);
    i = ClearList(&L);
    printf("\n清空L后：ListLength(L)=%d\n", ListLength(L));
    CreateListHead(&L, 20);
    printf("整體創(chuàng)建L的元素(頭插法)：");
    ListTraverse(L);
    i = ClearList(&L);
    printf("\n刪除L后：ListLength(L)=%d\n", ListLength(L));
    CreateListTail(&L, 20);
    printf("整體創(chuàng)建L的元素(尾插法)：");
    ListTraverse(L);
    return 0;
}

到此這篇關(guān)于c語言線性表全面梳理操作方法的文章就介紹到這了,更多相關(guān)c語言線性表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: