c語言實作順序表的基本操作

順序表就是用一段位址連續的存儲單元依次存儲資料元素，其實體的相連的。

是不是很類似數組的結構呢？

其優點就是可以通過下标直接随機通路。

代碼實作：

順序表結構封裝和函數聲明在List.h中，我實作的是動态開辟的，其中順序表中的結構封裝有data作為資料數組，length表示順序表空間，size為元素個數；

#ifndef _LIST_H_
#define _LIST_H_
/*
動态配置設定線性表順序存儲結構
實體結構:存儲結構相連
便于直接随機通路某個節點
*/
#define MAXSIZE 20//存儲空間
#define OK 1//函數狀态傳回值,成功傳回1,不成功傳回0
#define ERROR 0//
#define TRUE 1//真假值，真為1,假為0
#define FALSE 0
typedef int Status;//Status是函數類型，其值是函數結果狀态代碼 
typedef int ElemType;
typedef struct
{
	ElemType *data;
	size_t length;
	size_t size;
}SeqList;
void InitList(SeqList*L);//初始化線性表
void Destory(SeqList *L);//銷毀線性表
void ClearList(SeqList *L);//重置線性表
Status ListEmpty(SeqList L);//線性表是否為空
int ListLength(SeqList L);//傳回線性表中元素的個數
ElemType *GetElem(SeqList *L, int i, ElemType *e);//取第i個元素的值傳回給e
Status LocateElem(SeqList L, ElemType e);//在L中查找和e元素值相等的資料元素，不存在傳回0，成功傳回查找成功
Status ListInsert(SeqList *L, int i, ElemType e);//線上性表L中第i個位置插入新元素e
void ListDelete(SeqList *L, int i, ElemType *e);//删除線性表L中第i個位置元素e
void ListPrint(SeqList *L);
#endif
           

List.c函數實作檔案：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"List.h"
void InitList(SeqList*L)
{
	assert(L != NULL);
	L->data = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
	L->length = MAXSIZE;
	L->size = 0;
}
void Destory(SeqList *L)
{
	assert(L != NULL);
	if (L->data != NULL)
	{
		free(L->data);
		L->data = NULL;
	}
	L->size = 0;
	L->length = 0;
}
void ClearList(SeqList *L)
{
	assert(L != NULL);
	L->size = 0;
}
Status ListEmpty(SeqList L)
{
	return L.size == 0 ? TRUE : FALSE;
}
int ListLength(SeqList L)
{
	return L.size;
}
ElemType* GetElem(SeqList *L, int i, ElemType *e)
{
	assert(L != NULL &&i<=L->size);
	*e=L->data[i - 1];
	return e;
}

Status LocateElem(SeqList L, ElemType e)
{
	int i = 0;
	for (i = 0; i < L.size; i++)
	{
		if (L.data[i] == e)
		{
			return OK;//查找到與e相等的元素值
		}
	}
	return ERROR;//沒有與e元素值相等的值
}
Status ListInsert(SeqList *L, int i, ElemType e)
{
	assert(L != NULL);
	if (L->size + 1 > L->length)
	{
		L->length+= MAXSIZE;
		ElemType* new = (ElemType*)realloc(L->data, sizeof(ElemType)*L->length);//擴容，增加配置設定空間
		if (new == NULL)
		{
			return ERROR;
		}
		L->data = new;
	}
	int j = L->size;
	for (j = L->size; j > i-1; j--)
	{
		L->data[j] = L->data[j-1];
	}
	L->size++;
	L->data[j] = e;
	return OK;
}
void ListDelete(SeqList *L, int i, ElemType *e)
{
	assert(L != NULL);
	if (i > L->size || i<=0)
	{
		return;
	}
	int j = 0;
	*e = L->data[i - 1];
	for (j = i - 1; j <= L->size; j++)
	{
		L->data[j] = L->data[j + 1];
	}
	L->size--;
}

void ListPrint(SeqList *L)
{
	assert(L != NULL);
	int i = 0;
	for (i = 0; i <L->size; i++)
	{
		printf("%d ", L->data[i]);
	}
	printf("\n");
}

void TestList()//測試函數
{
	SeqList sq;
	ElemType val=0;
	InitList(&sq);
	ListPrint(&sq);
	bool b=ListEmpty(sq);
	printf("bool b:%d \n", b);
	ListInsert(&sq, 1, 1);
	ListInsert(&sq, 2, 2);
	ListInsert(&sq, 3, 3);
	ListInsert(&sq, 4, 4);
	ListInsert(&sq, 5, 5);
	ListPrint(&sq);
	ListInsert(&sq, 3, 8);
	ListPrint(&sq);
	ListDelete(&sq, 2, &val);
	printf("删除元素的資料為：%d\n", val);
	ListPrint(&sq);
	int n=ListLength(sq);
	printf("sq中的元素個數為：%d\n", n);
	b=ListEmpty(sq);
	printf("bool b；%d\n", b);
	b=LocateElem(sq, 10);
	printf("bool b；%d\n", b);
	b = LocateElem(sq, 4);
	printf("bool b；%d\n", b);
	Destory(&sq);
}
int main()
{
	TestList();

	return 0;
}
           

代碼雖然已經實作，但是在實作過程中我們還要注意一些問題：

在插入元素的時候需要注意插入位置是否合理，是否滿足0<i<=size+1,插入之前空間是否充足，是否需要擴容？

在删除第某個元素是，該下标是否存在 0<i<size

其中測試函數的列印結果為：

當然順序表也有不足：

• 在插入和删除時時間複雜度為O(n)，
• 增容需要申請新空間，銷毀舊空間，會有一定的消耗