天天看點
傳回

用C語言實作順序表1、線性表2、順序表

資料結構學習開始，沖沖沖

文章目錄

  • 1、線性表
  • 2、順序表
    • 2.1 概念及結構
    • 2.2 接口實作
      • 2.2.1：順序表的建立
        • 靜态順序表的建立：
        • 動态順序表的建立：
      • 2.2.2：順序表的初始化
      • 2.2.3：順序表的銷毀
      • 2.2.4：順序表的尾插
      • 2.2.5：順序表的列印
      • 2.2.6：順序表的尾删
      • 2.2.7：順序表的頭插
      • 2.2.8：順序表的頭删
      • 2.2.9：順序表查找
      • 2.2.10：順序表在pos位置插入x
      • 2.2.11：順序表删除pos位置的值
      • 2.2.12：順序表删除pos位置的值
      • 2.2.12：順序表删除所有指定的值
    • 2.3 程式源
      • `test.c`
      • `seqlist.c`
      • `seqlist.h`

1、線性表

線性表（

linear list

）是n個具有相同特性的資料元素的有限序列。 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、連結清單、棧、隊列、字元串…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在實體結構上并不一定是連續的，線性表在實體上存儲時，通常以數組和鍊式結構的形式存儲

例如：

  1. 順序表：邏輯上是線性，實體上也是連續的
  2. 連結清單：邏輯上是線性，實體上是不連續的
用C語言實作順序表1、線性表2、順序表

2、順序表

2.1 概念及結構

順序表是用一段實體位址連續的存儲單元依次存儲資料元素的線性結構，一般情況下采用數組存儲。在數組上完成資料的增删查改。

  • 順序表一般可以分為：
      1. 靜态順序表：使用定長數組存儲元素（之前的靜态通訊錄）
        用C語言實作順序表1、線性表2、順序表
      1. 動态順序表：使用動态開辟的數組存儲
        用C語言實作順序表1、線性表2、順序表

2.2 接口實作

寫一個函數就要調試一下看看寫的是否完全正确！！！！

尾插的時間複雜度是O(1),直接動最後一個就行了

頭插需要從最後一個開始挪，是以他的時間複雜度是O(N).

是以我們在用的時候一般都用尾插

2.2.1：順序表的建立

需要建立一個小項目工程

建立三個檔案

⭐

seqlist.h

放順序表的頭檔案，函數聲明

⭐

seqlist.c

放順序表的函數

⭐

test.c

 是主函數。存放架構

靜态順序表的建立： 

define N 8
typedef int DataType; //重新命名一下，後續修改資料類型會很友善
//靜态順序表
typedef struct Seqlist
{
	int a[N];
	int size;//記錄存儲多少個有效資料
}SeqList;//重新命名一下讓後面的操作更加友善
靜态順序表缺點：靜态順序表隻适用于确定知道需要存多少資料的場景。靜态順序表的定長數組導緻N定大了，空間開多了浪費，開少了不夠用。是以現實中基本都是使用動态順序表，根據需要動态的配置設定空間大小，是以下面我們實作動态順序表

動态順序表的建立：

想用多少就開多少空間，不會造成空間的浪費，非常友善

typedef int DataType;

typedef struct SeqList
{
	DataType* a;  //指向動态開辟的數組
	int size;     //有效個數
	int capacity;  //容量空間大小
}SeqList;

2.2.2：順序表的初始化 

// 順序表初始化
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

2.2.3：順序表的銷毀

為了防止後續測試時會記憶體洩漏，是以現在就把銷毀函數搞定了。由于

數組a

是後續動态開辟的，是以要

free

掉。

// 順序表銷毀
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

2.2.4：順序表的尾插

順序表尾插前需要動态開辟一個數組，然後再依次插入。但是插入資料總會有空間滿了時候，是以還需要一個函數判斷空間是是否滿了，如果滿了，則增容，将空間

realloc

為原來的兩倍。

// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//如果一開始空間是0，則開辟4個空間，不一定是整型，要根據自己typedef的資料類型決定，否則開辟原有的兩倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		SeqList* temp = (SeqList*)realloc(ps->a, newcapacity * sizeof(DataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = temp;  //開辟成功
		ps->capacity = newcapacity;
	}
}

// 順序表尾插
void SeqListPushBack(SeqList* ps, DataType x)
{
	assert(ps);
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.2.5：順序表的列印

該操作就是簡單列印一下，我們每寫一個部分，我們就檢查一部分，列印就是為了看我們寫的最後的效果達到了沒有，這個非常簡單，大家直接看代碼。

⭐對于這個部分，我們需要提醒一下大家，不要等我們将全部代碼寫完在進行調試，我們寫一個部分就測試一部分，看看這個部分有沒有問題，沒有問題我們再進行下一部分。

// 順序表列印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

2.2.6：順序表的尾删

大家可能想能不能直接将最後一個資料直接變成0，是不是将相當于将最後一個資料删除了呢？但是大家可以這樣想，本來人家原本的資料就是0，那你再改成0，好像什麼都沒做！

其實可以直接将

sz–1

，不就巧妙的将最後一個資料删掉了嗎，有的人想不明白的，他明明還在哪呀，怎麼叫删掉了呢，其實你

sz–1

，你不用他了，下一回插入的時候不就直接覆寫掉了嗎？

// 順序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size); //防止資料為空
	ps->size--;
}

2.2.7：順序表的頭插

  1. 頭插資料和尾插一樣都要判滿
  2. **差異：**頭插資料需要挪動資料，将資料整體向後挪動一個機關 
// 順序表頭插
void SeqListPushFront(SeqList* ps, DataType x)
{
	assert(ps);
	CheckCapacity(ps); //判滿

	int i = ps->size;
	while (i)
	{
		ps->a[i] = ps->a[i - 1]; //挪資料
		i--;
	}
	ps->a[i] = x;   //頭插入資料，此時i=0;
	ps->size++;
}

2.2.8：順序表的頭删 

// 順序表頭删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size); //防止資料為空

	//挪資料
	int i = 1;
	for (i = 1; i < ps->size; i++)
	{
		ps->a[i - 1] = ps->a[i];
	}
	ps->size--;
}
  1. 頭删資料和尾删一樣都要斷言，防止資料為空
  2. **差異：**頭删資料需要挪動資料，将資料整體向前挪動一個機關

2.2.9：順序表查找

要在指定位置插入和删除資料前要找到資料的位置，我們可以設計一個函數完成這個功能。找到了，傳回這個元素的下标，找不到則傳回-1； 
// 順序表查找
int SeqListFind(SeqList* ps, DataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}

	}
	return -1;
}

2.2.10：順序表在pos位置插入x

  1. pos是SeqListFind後傳回的位置
  2. pos位置插入資料是，插入後的資料在pos處！！ 
// pos是SeqListFind後傳回的位置。
//插入資料是，讓插入後的資料在pos處
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, DataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);  //檢查pos的有效性

	CheckCapacity(ps); //判滿

	int i = ps->size;
	for (i = ps->size; i >= pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}

是以：可以使用

SeqListInsert

去複用頭插和尾插！！

// 順序表尾插
void SeqListPushBack(SeqList* ps, DataType x)
{
	assert(ps);
	//CheckCapacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;

	SeqListInsert(ps, ps->size, x);
}
           
// 順序表頭插
void SeqListPushFront(SeqList* ps, DataType x)
{
	assert(ps);

	//CheckCapacity(ps); //判滿

	挪資料
	//int i = ps->size;
	//while (i)
	//{
	//	ps->a[i] = ps->a[i - 1]; 
	//	i--;
	//}
	//ps->a[i] = x;   //頭插入資料，此時i=0;
	//ps->size++;

	SeqListInsert(ps, 0, x);
}

2.2.11：順序表删除pos位置的值

同樣需要檢查順序表是否為空以及pos的有效性

// 順序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size); //防止資料為空
	assert(pos >= 0 && pos <= ps->size);  //檢查pos的有效性

	//挪資料
	int i = pos ;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

是以：可以使用

SeqListErase

去複用頭删和尾删！！

// 順序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);

	//assert(ps->size); //防止資料為空
	//ps->size--;

	SeqListErase(ps, ps->size);
}
           
// 順序表頭删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	//assert(ps->size); //防止資料為空

	挪資料
	//int i = 1;
	//for (i = 1; i < ps->size; i++)
	//{
	//	ps->a[i - 1] = ps->a[i];
	//}
	//ps->size--;

	SeqListErase(ps, 0);
}

2.2.12：順序表删除pos位置的值 

// 順序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size); //防止資料為空
	assert(pos >= 0 && pos <= ps->size);  //檢查pos的有效性

	//挪資料
	int i = pos ;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

2.2.12：順序表删除所有指定的值

思路：需要寫一個由起始位置查找任意元素的函數。beign先從0開始，找到第一個後删除，然後更新beign的位置，此時beign=pos。即再從pos處開始查找。

//設定始位置查找任意元素
int SeqListFindBeign(SeqList* ps, DataType x, int beign)
{
	assert(ps);
	int i = beign;

	for (i = beign; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

測試代碼：

//删除所有指定的值
void test6(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	int pos = SeqListFindBeign(ps, 2, 0);   //找到2的位置并傳回
	while (pos != -1)
	{
		SeqListErase(ps, pos);//删除
		pos = SeqListFindBeign(ps, 2, pos);  //從pos處繼續找
	}
	SeqListPrint(ps);  //列印


	SeqListDestory(ps);  //銷毀
}

2.3 程式源

test.c

 

#define _CRT_SECURE_NO_WARNINGS 1
#include "seqlist.h"


//檢查尾插和尾删
void test1(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushBack(ps, 1); //尾插
	SeqListPushBack(ps, 2);
	SeqListPushBack(ps, 3);
	SeqListPushBack(ps, 4);
	SeqListPushBack(ps, 5);
	SeqListPrint(ps);  //列印

	SeqListPopBack(ps);  //尾删
	SeqListPrint(ps);   //列印

	SeqListDestory(ps);  //銷毀
}

//檢查頭插和頭删
void test2(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 4);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	SeqListPopFront(ps);  //頭删
	SeqListPrint(ps);   //列印

	SeqListDestory(ps);  //銷毀
}

//查找資料是否存在
void test3(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 4);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	int ret = SeqListFind(ps, 2);
	if (ret != -1)
	{
		printf("該資料存在,下标為%d\n", ret);
	}
	else
	{
		printf("該資料不存在\n");
	}

	SeqListDestory(ps);  //銷毀
}

//任意位置插入
void test4(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 4);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	int pos = SeqListFind(ps, 2); //找到2的位置并傳回
	if (pos != -1)
	{
		SeqListInsert(ps, pos, 100);
		SeqListPrint(ps);  //列印
	}
	else
	{
		printf("該資料不存在\n");
	}

	SeqListDestory(ps);  //銷毀
}

//任意位置删除
void test5(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 4);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	int pos = SeqListFind(ps, 2); //找到2的位置并傳回
	if (pos != -1)
	{
		SeqListErase(ps, pos);
		SeqListPrint(ps);  //列印
	}
	else
	{
		printf("該資料不存在\n");
	}

	SeqListDestory(ps);  //銷毀
}


//删除所有指定的值
void test6(SeqList* ps)
{
	SeqListInit(ps);

	SeqListPushFront(ps, 1); //頭插
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 3);
	SeqListPushFront(ps, 2);
	SeqListPushFront(ps, 5);
	SeqListPrint(ps);  //列印

	int pos = SeqListFindBeign(ps, 2, 0);   //找到2的位置并傳回
	while (pos != -1)
	{
		SeqListErase(ps, pos);//删除
		pos = SeqListFindBeign(ps, 2, pos);  //從pos處繼續找
	}
	SeqListPrint(ps);  //列印


	SeqListDestory(ps);  //銷毀
}



int main()
{
	SeqList s;
	test6(&s);

	return 0;
}

seqlist.c

 

#define _CRT_SECURE_NO_WARNINGS 1

#include "seqlist.h"

// 順序表初始化
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


// 順序表銷毀
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//如果一開始空間是0，則開辟4個空間，不一定是整型，要根據自己typedef的資料類型決定，否則開辟原有的兩倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		DataType* temp = (DataType*)realloc(ps->a, newcapacity * sizeof(DataType));
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = temp;  //開辟成功
		ps->capacity = newcapacity;
	}
}

// 順序表尾插
void SeqListPushBack(SeqList* ps, DataType x)
{
	assert(ps);
	//CheckCapacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;

	SeqListInsert(ps, ps->size, x);
}


// 順序表列印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

// 順序表尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);

	//assert(ps->size); //防止資料為空
	//ps->size--;

	SeqListErase(ps, ps->size);
}

// 順序表頭插
void SeqListPushFront(SeqList* ps, DataType x)
{
	assert(ps);

	//CheckCapacity(ps); //判滿

	挪資料
	//int i = ps->size;
	//while (i)
	//{
	//	ps->a[i] = ps->a[i - 1]; 
	//	i--;
	//}
	//ps->a[i] = x;   //頭插入資料，此時i=0;
	//ps->size++;

	SeqListInsert(ps, 0, x);
}


// 順序表頭删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	//assert(ps->size); //防止資料為空

	挪資料
	//int i = 1;
	//for (i = 1; i < ps->size; i++)
	//{
	//	ps->a[i - 1] = ps->a[i];
	//}
	//ps->size--;

	SeqListErase(ps, 0);
}


// 順序表查找
int SeqListFind(SeqList* ps, DataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}

	}
	return -1;
}


// pos是SeqListFind後傳回的位置。
//插入資料是，讓插入後的資料在pos處
// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, DataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);  //檢查pos的有效性

	CheckCapacity(ps); //判滿

	int i = ps->size;
	for (i = ps->size; i >= pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}


// 順序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(ps->size); //防止資料為空
	assert(pos >= 0 && pos <= ps->size);  //檢查pos的有效性

	//挪資料
	int i = pos ;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}


//設定起始位置查找任意元素
int SeqListFindBeign(SeqList* ps, DataType x, int beign)
{
	assert(ps);
	int i = beign;

	for (i = beign; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

seqlist.h

 

#pragma once

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

typedef int DataType;

typedef struct SeqList
{
	DataType* a;  //指向動态開辟的數組
	int size;     //有效個數
	int capacity;  //容量空間大小
}SeqList;


// 順序表初始化
void SeqListInit(SeqList * ps);
// 順序表銷毀
void SeqListDestory(SeqList* ps);


// 檢查空間，如果滿了，進行增容
void CheckCapacity(SeqList* ps);
// 順序表尾插
void SeqListPushBack(SeqList* ps, DataType x);

// 順序表列印
void SeqListPrint(SeqList* ps);

// 順序表尾删
void SeqListPopBack(SeqList* ps);




// 順序表頭插
void SeqListPushFront(SeqList* ps, DataType x);
// 順序表頭删
void SeqListPopFront(SeqList* ps);


// 順序表查找
int SeqListFind(SeqList* ps, DataType x);

// 順序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, DataType x);
// 順序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);


//設定起始位置查找任意元素
int SeqListFindBeign(SeqList* ps, DataType x, int beign);
資料結構初階(C語言) c語言 資料結構 連結清單
上一篇: 2023年電動汽車輕量化材料行業頭部企業市場占有率及排名調研報告
下一篇: 10款JavaScript 資料可視化庫

繼續閱讀