C語言的線性表之順序表你瞭解嗎

Posted on by

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

概念

線性表的順序表示指的是用一組地址連續的存儲單元依次存儲線性表中的數據元素，這種表示也稱做線性表的順序儲存結構或順序映像。通常，稱這種存儲結構的線性表為順序表 (Sequential List) 。其特點是，邏輯上相鄰的數據元素，其物理次序也是相鄰的。

1. 順序表的儲存結構

#include <stdio.h>#include <stdlib.h>#include <assert.h>#define MAX_SIZE 1000 //順序表能儲存的最大數值typedef int DATA;   //抽象化int類型typedef struct _List{    DATA *data;    int length;} SeqList;#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MAX_SIZE 1000 //順序表能儲存的最大數值
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;  //順序表的初始長度為0
    assert(list->data != NULL);
    return list;
}

2.1 順序表的插入

頭插法：

1.將表中所有數據元素向後移一位

2.將數據元素插入第 0 位

3.長度 length + 1

圖解

代碼

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

指定位置插入法：

1.將第 index 位與它後面的所有數據元素向後移動一位

2.將數據元素插入第 index 位

3.長度 length + 1

圖解

在這裡插入圖片描述

代碼

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

尾插法：

1.將數據插入第 length 位

2.長度 length + 1

圖解

代碼

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

2.2 順序表的查找

步驟

通過數值逐個比對，若表中存在相同元素則返回較前面的元素位置。

代碼

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 順序表的刪除

通過值刪除元素

1.找到值對應的元素下標 index

2.將第 index + 1 位與它後面的所有元素向前移動一位

3.長度 length – 1

圖解

在這裡插入圖片描述

代碼

void deleteByData(SeqList* list, DATA data) {
	if (list->length == 0){
      	printf("表為空，無需進行刪除...\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("該數據不存在，無法刪除...\n");
  	}
}

通過索引刪除元素

1.將第 index + 1 位與它後面的所有元素向前移動一位

2.長度 length – 1

圖解

代碼

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

總結

本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!    

推薦閱讀：