快捷導(dǎo)航

C語(yǔ)言的線性表之順序表你了解嗎

更新時(shí)間：2022年02月09日 14:49:12 作者：IAmZero.

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言的線性表之順序表，線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，本文具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

線性表 —— 順序表 (C語(yǔ)言)

概念

線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，這種表示也稱做線性表的順序儲(chǔ)存結(jié)構(gòu)或順序映像。通常，稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表 (Sequential List) 。其特點(diǎn)是，邏輯上相鄰的數(shù)據(jù)元素，其物理次序也是相鄰的。

1. 順序表的儲(chǔ)存結(jié)構(gòu)

#include <stdlib.h>
#include <assert.h>
#define MAX_SIZE 1000 //順序表能儲(chǔ)存的最大數(shù)值
typedef int DATA;   //抽象化int類型
typedef struct _List{
    DATA *data;
    int length;
} SeqList;

2. 順序表的基本操作

//初始化順序表
SeqList* initList() {
    SeqList* list = malloc(sizeof(SeqList));
  	assert(list != NULL);
    list->data = malloc(MAX_SIZE * sizeof(DATA));
    list->length = 0;  //順序表的初始長(zhǎng)度為0
    assert(list->data != NULL);
    return list;
}

2.1 順序表的插入

頭插法：

1.將表中所有數(shù)據(jù)元素向后移一位

2.將數(shù)據(jù)元素插入第 0 位

3.長(zhǎng)度 length + 1

圖解

代碼

void insertByHead(SeqList* list, DATA data){
    if (list->length >= MAX_SIZE){
        printf("順序表已滿無(wú)法插入數(shù)據(jù)...\n");
        return; //跳出函數(shù)
    }
    for (int i = list->length; i > 0; i--){
        list->data[i] = list->data[i-1];
    }
    list->data[0] = data;
    list->length++;
}

指定位置插入法：

1.將第 index 位與它后面的所有數(shù)據(jù)元素向后移動(dòng)一位

2.將數(shù)據(jù)元素插入第 index 位

3.長(zhǎng)度 length + 1

圖解

在這里插入圖片描述

代碼

void insertByIndex(SeqList* list, int index, DATA data){
    if ((index < 0 || index >= list->length) && list->length >= MAX_SIZE){
        printf("輸入的index值錯(cuò)誤或順序表已滿無(wú)法插入...\n");
        return; //跳出函數(shù)
    }
    for (int i = list->length; i > index; i--) {
	    list->data[i] = list->data[i - 1];
    }
    list->data[index] = data;
    list->length++;
}

尾插法：

1.將數(shù)據(jù)插入第 length 位

2.長(zhǎng)度 length + 1

圖解

代碼

void insertByTail(SeqList* list, DATA data){    if (list->length >= MAX_SIZE){        printf("順序表已滿無(wú)法插入數(shù)據(jù)...\n");        return; //跳出函數(shù)    }    list->data[list->length++] = data;}void insertByTail(SeqList* list, DATA data){
    if (list->length >= MAX_SIZE){
        printf("順序表已滿無(wú)法插入數(shù)據(jù)...\n");
        return; //跳出函數(shù)
    }
    list->data[list->length++] = data;
}

2.2 順序表的查找

步驟

通過(guò)數(shù)值逐個(gè)比對(duì)，若表中存在相同元素則返回較前面的元素位置。

代碼

int find(SeqList* list, DATA data)
{
	for (int i = 0; i < list->length; i++) {
		if (list->data[i] == data) {
			return i;
		}
	}
	return -1;
}

2.3 順序表的刪除

通過(guò)值刪除元素

1.找到值對(duì)應(yīng)的元素下標(biāo) index

2.將第 index + 1 位與它后面的所有元素向前移動(dòng)一位

3.長(zhǎng)度 length - 1

圖解

在這里插入圖片描述

代碼

void deleteByData(SeqList* list, DATA data) {
	if (list->length == 0){
      	printf("表為空，無(wú)需進(jìn)行刪除...\n");
    }
	int ret = find(list, data);
	if (ret != -1) {
		for (int i = ret; i < list->length - 1; i++) {
			list->data[i] = list->data[i + 1];
		}
		list->length--;
	}
  	else{
    	printf("該數(shù)據(jù)不存在，無(wú)法刪除...\n");
  	}
}

通過(guò)索引刪除元素

1.將第 index + 1 位與它后面的所有元素向前移動(dòng)一位

2.長(zhǎng)度 length - 1

圖解

代碼

void deleteByIndex(SeqList* list, int index) {
	if (list->length == 0){
      	printf("表為空，無(wú)需進(jìn)行刪除...\n");
    }
  	if (index >= list->length){
    	printf("索引位置大于表的總長(zhǎng)度...\n");
      	return;
  	}
	for (int i = index; i < list->length - 1; i++) {
		list->data[i] = list->data[i + 1];
	}
	list->length--;
}