1.摘要

本文主要介紹什么是線性表和線性表中的第一類資料結構------順序表的描述以及實作，

2.什么是線性表

大家在學校上課的時候，每當上課鈴響，老師總是會手持一張點名表，一個一個地點同學的名字，細心的你有沒有發現，老師每次上課點名的順序總是一致的，

這不是廢話嗎？那為什么我總是最后一個被點到呢？哦！原來老師是按照學號由小到大對班上的50多個人進行點名的！我的學號是最大的！

老師手中的點名表，實際上就是一張線性表，每位同學的資訊就像被一根看不見的線串了起來，從頭到尾連續排放，而對于線上串接的資料元素，則是：{學號姓名}

在這里插入圖片描述

我們給出線性表的定義：線性表是n個具有相同特性的資料元素組成的有限序列

我們應當強調：

線性表中每個資料元素都應是相同的型別，可以是一個整型，也可以是一個復雜一點的結構體，正如上面的學生資訊，
線性表是有限長度的，
線性表是一個序列，也就是說，元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最后一個元素無后繼，其他每個元素都有且只有一個前驅和后繼，

若將線性表記為（a₁,…,a_i-1,a_i,a_i+1,…,a_n），圖示則為：
在這里插入圖片描述
好啦，那讓我們來學習一下最簡單的線性表------順序表吧！

3.什么是順序表

由于順序表是線性表的一種，我們很容易猜到，在邏輯上，順序表中的一個個資料元素是連續的，

程式中的資料存放在記憶體中，那么這些邏輯連續的資料，在物理上是怎么排列的呢？是連續的還是不連續的呢？

對于順序表，或者說我們的順序存盤結構而言，“順序”二字告訴我們，順序表中的資料在物理地址上是連續存放的，

我們給出順序表的定義：用一段地址連續的存盤單元依次存盤資料元素的線性結構，

一般地，為了實作物理連續，我們采用陣列來實作順序表，進行資料的增刪查改，

在這里插入圖片描述

上圖顯示了資料的順序存盤結構，我們可以看到，資料元素的地址在物理上是連續的，

4.順序表的代碼實作

4.1概念及結構

首先，我們可以根據順序表存盤資料數量是否固定，將順序表分為兩類：

靜態順序表：使用定長陣列存盤資料，如在開頭定義陣列長度識別符號：
#define LENGTH 10
動態順序表：使用動態開辟的陣列存盤資料

為了使得資料存盤的靈活，我們采用動態順序表，

接下來，我們思考一下，我們怎么做才能方便的進行增刪查改操作呢？

需要一個指標，指向陣列，以便操作陣列
用變數記錄當前動態開辟元素的個數
快速找到當前元素位置------>用變數記錄當前位置下標

想想看，我們與其孤零零地創建以上三個變數，倒不如把它們集成在一個結構體變數中，想想也整齊：

typedef struct SeqList {
	SeqListDataType* ptr;
	int capacity;
	int sz;
}SeqList;

讓我們再來看看我們需要的增刪查改等操作的介面：

// 順序表初始化
void SeqListInit(SeqList* ps);
// 順序表尾插
void SeqListPushBack(SeqList* ps, SeqListDataType x);
// 順序表頭插
void SeqListPushFront(SeqList* ps, SeqListDataType x);
// 順序表列印
void SeqListPrint(const SeqList* ps);
// 順序表尾刪
void SeqListPopBack(SeqList* ps);
// 順序表頭刪
void SeqListPopFront(SeqList* ps);
// 順序表銷毀
void SeqListDestroy(SeqList* ps);
// 查找順序表中某個元素
int SeqListFind(const SeqList* ps, SeqListDataType x);
// 順序表在pos位置處插入x
void SeqListInsert(SeqList* ps, size_t pos, SeqListDataType x);
// 洗掉順序表pos位置的元素
void SeqListErase(SeqList* ps, size_t pos);
// 升序
void SeqListSortUp(SeqList* ps);
// 降序
void SeqListSortDown(SeqList* ps);

4.2頭檔案

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SeqListDataType;
#define INIT_SZ 4
typedef struct SeqList {
	SeqListDataType* ptr;
	int capacity;
	int sz;
}SeqList;

void SeqListInit(SeqList* ps);
void SeqListPushBack(SeqList* ps, SeqListDataType x);
void SeqListPushFront(SeqList* ps, SeqListDataType x);
void SeqListPrint(const SeqList* ps);
void SeqListPopBack(SeqList* ps);
void SeqListPopFront(SeqList* ps);
void SeqListDestroy(SeqList* ps);
int SeqListFind(const SeqList* ps, SeqListDataType x);
void SeqListInsert(SeqList* ps, size_t pos, SeqListDataType x);
void SeqListErase(SeqList* ps, size_t pos);
void SeqListSortUp(SeqList* ps);
void SeqListSortDown(SeqList* ps);

4.3介面檔案

#include"squelist.h"


void SeqListCheckCap(SeqList* ps)
{
	assert(ps);
	if (ps->sz == ps->capacity)
	{
		SeqListDataType* tmp = realloc(ps->ptr, 2 * ps->capacity * sizeof(SeqListDataType));
		ps->capacity *= 2;
		if (tmp)
		{
			ps->ptr = tmp;
		}
	}
	if (ps->capacity > 4 * ps->sz && ps->sz != 0 )
	{
		SeqListDataType* tmp = realloc(ps->ptr, (ps->capacity / 2) * sizeof(SeqListDataType));
		ps->capacity /= 2;
		if (tmp)
		{
			ps->ptr = tmp;
		}
	}

}

int SortDown(SeqListDataType* e1, SeqListDataType* e2)
{
	return *e2 - *e1;
}

int SortUp(SeqListDataType* e1,SeqListDataType* e2)
{
	return *e1 - *e2;
}
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->ptr = (SeqListDataType*)malloc(INIT_SZ * sizeof(SeqListDataType));
	if (ps->ptr)
	{
		ps->capacity = INIT_SZ;
		ps->sz = 0;
	}	
}

void SeqListDestroy(SeqList* ps)
{
	ps->sz = 0;
	ps->capacity = 0;
	free(ps->ptr);
	ps->ptr = NULL;
}

void SeqListPushBack(SeqList* ps, SeqListDataType x)
{
	assert(ps);
	SeqListCheckCap(ps);
	ps->ptr[ps->sz] = x;
	ps->sz++;
}

void SeqListPushFront(SeqList* ps, SeqListDataType x)
{
	assert(ps);
	SeqListCheckCap(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		ps->ptr[ps->sz - i] = ps->ptr[ps->sz - i - 1];
	}
	ps->ptr[0] = x;
	ps->sz++;
}

void SeqListPrint(const SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->ptr[i]);
	}
	printf("\n");
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	SeqListCheckCap(ps);
	SeqListCheckCap(ps);
	ps->sz--;
}
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	SeqListCheckCap(ps);
	int i = 0;
	for (i = 0; i < ps->sz - 1; i++)
	{
		ps->ptr[i] = ps->ptr[i - 1];
	}
	ps->sz--;
}

int SeqListFind(const SeqList* ps,SeqListDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (x == ps->ptr[i])
		{
			return 1;
		}
	}
	return 0;
}

void SeqListInsert(SeqList* ps, size_t pos, SeqListDataType x)
{
	assert(ps);
	SeqListCheckCap(ps);
	SeqListCheckCap(ps);
	int i = 0;
	for (i = 0; i < ps->sz - pos + 1; i++)
	{
		ps->ptr[ps->sz - i] = ps->ptr[ps->sz - i - 1];
	}
	ps->ptr[pos - 1] = x;
	ps->sz++;
}

void SeqListErase(SeqList* ps, size_t pos)
{
	assert(ps);
	SeqListCheckCap(ps);	
	int i = 0;
	for (i = 0; i < ps->sz - pos; i++)
	{
		ps->ptr[pos + i - 1] = ps->ptr[pos + i];
	}
	ps->sz--;
}

void SeqListSortUp(SeqList* ps)
{
	assert(ps);
	qsort(ps->ptr, ps->sz, sizeof(SeqListDataType), SortUp);

}

void SeqListSortDown(SeqList* ps)
{
	assert(ps);
	qsort(ps->ptr, ps->sz, sizeof(SeqListDataType), SortDown);
}

4.4測驗檔案

#include"squelist.h"

void Test()
{
	SeqList sl;
	SeqList* p = &sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPrint(&sl);
	SeqListPushBack(&sl, 2);
	SeqListPrint(&sl);
	SeqListPushFront(&sl,3);
	SeqListPrint(&sl);
	SeqListPushFront(&sl, 3);
	SeqListPrint(&sl);
	SeqListPushFront(&sl, 3);
	SeqListPrint(&sl);
	SeqListInsert(&sl, 4, 9);
	SeqListPrint(&sl);
	SeqListErase(&sl, 4);
	SeqListPrint(&sl);
	SeqListSortUp(&sl);
	SeqListPrint(&sl);
	SeqListSortDown(&sl);
	SeqListPrint(&sl);

	if (SeqListFind(&sl, 3) == 1)
		printf("3 yes\n");
	else
		printf("3 no\n");

	if (SeqListFind(&sl, 9) == 1)
		printf("9 yes\n");
	else
		printf("9 no\n");

	SeqListDestroy(&sl);
}


int main()
{
	Test();
	return 0;
}

5.參考文獻

1.《大話資料結構》第三章 p42

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298997.html

標籤：其他

上一篇：??機器學習入門??(三) 圖解K-Means聚類演算法 | 附加小練習

下一篇：Github之First day on Github，純手敲萬字，帶你學習并完成任務點，超詳細教程！（上）

【資料結構】線性表之順序表

目錄