天天看點
傳回

【C語言】C語言實作靜态順序表

     在我們學習C語言的過程中，會遇到線性表，這本來應該屬于資料結構的一部分，但是也能通過C語言來解決。所謂線性表，就是定義一張順序表也就是在記憶體中開辟一段連續的存儲空間，并給它一個名字進行辨別。隻有定義了一個順序表，才能利用該順序表存放資料元素，也才能對該順序表進行各種操作。 順序表的實作和靜态通訊錄相似，通訊錄的實作已經在前面的部落格中為大家總結（【通訊錄】點選打開連結）。下面附上順序表的代碼，部分問題已經在代碼中給予解釋。

SeqList.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

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

#define MAX 10

typedef int DataType;

typedef struct SeqList
{
	int sz;
	DataType data[MAX];
}SeqList, *pSeqList;

void InitSeqList(pSeqList ps);//初始化
void PushBack(pSeqList ps, DataType d);//尾部添加
void PopBack(pSeqList ps);//尾部删除
void Display(const pSeqList ps);//列印
void PushFront(pSeqList ps, DataType d);//頭部添加
void PopFront(pSeqList ps);//頭部删除
int Find(pSeqList ps, DataType d);//查找
void Insert(pSeqList ps, DataType d, int pos);//在順序表某位置插入某個元素
void Remove(pSeqList ps, DataType d);//删除某一個特定元素
void RemoveAll(pSeqList ps, DataType d);//删除順序表中出現的所有的特定元素
void Reverse(pSeqList ps);//逆序
void Sort(pSeqList ps);//排序（升序）
int BinarySearch(pSeqList ps, DataType d);//二分查找
#endif//__SEQLIST_H_

SeqList.c

#include "SeqList.h"

//初始化
void InitSeqList(pSeqList ps)
{
	assert(ps != NULL);
	memset(ps->data, 0, MAX*sizeof(DataType));
	ps->sz = 0;
}

//尾部添加
void PushBack(pSeqList ps, DataType d)
{
	assert(ps != NULL);
	if (ps->sz == MAX)
	{
		return;
	}
	ps->data[ps->sz] = d;
	ps->sz++;
}

//尾部删除
void PopBack(pSeqList ps)
{
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	ps->sz--;
}

//列印
void Display(const pSeqList ps)
{
	int i = 0;
	assert(ps != NULL);
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d  ", ps->data[i]);
	}
	printf("\n");
}


//頭部添加
void PushFront(pSeqList ps, DataType d)
{
	assert(ps != NULL);
	if (ps->sz == MAX)
	{
		return;
	}
	memmove(ps->data + 1, ps->data, sizeof(DataType)*(ps->sz));
	ps->data[0] = d;
	ps->sz++;
}

//頭部删除
void PopFront(pSeqList ps)
{
	int i = 0;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	for (i = 0; i < ps->sz - 1; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->sz--;
}

//查找
int Find(pSeqList ps, DataType d)
{
	int i = 0;
	assert(ps != NULL);
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == d)
			return i;
	}
	return -1;
}

//
void Insert(pSeqList ps, DataType d, int pos)
{
	int i = 0;
	assert(ps != NULL);
	if (ps->sz == MAX)
	{
		return;
	}
	memmove(ps->data + pos + 1, ps->data + pos, (ps->sz - pos)*sizeof(DataType));
	ps->data[pos] = d;
	ps->sz++;
}

void Remove(pSeqList ps, DataType d)
{
	int pos = 0;
	assert(ps != NULL);
	pos = Find(ps, d);
	if (pos != -1)
	{
		memmove(ps->data + pos, ps->data + pos + 1, (ps->sz - pos - 1)*sizeof(DataType));
		ps->sz--;
	}
}


void RemoveAll(pSeqList ps, DataType d)
{
	int pos = 0;
	assert(ps != NULL);
	while ((pos = Find(ps, d)) != -1)
	{
		Remove(ps, d);
	}
}

void Reverse(pSeqList ps)
{
	int left = 0;
	int right = ps->sz - 1;
	DataType tmp = 0;
	if (ps->sz == 0)
	{
		return;
	}
	while (left < right)
	{
		tmp = ps->data[left];
		ps->data[left] = ps->data[right];
		ps->data[right] = tmp;
		left++;
		right--;
	}
}

void Sort(pSeqList ps)
{
	int i = 0;
	int j = 0;
	assert(ps);
	if (ps->sz == 0)
	{
		return;
	}
	for (i = 0; i < ps->sz - 1; i++)
	{
		for (j = 0; j < ps->sz - 1 - i; j++)
		{
			if (ps->data[j]>ps->data[j + 1])
			{
				DataType tmp = ps->data[j];
				ps->data[j] = ps->data[j + 1];
				ps->data[j + 1] = tmp;
			}
		}
	}
}
//二分法
int BinarySearch(pSeqList ps, DataType d)
{
	int left = 0;
	int right = ps->sz;
	int mid = left + ((right - left) >> 1);
	assert(ps);
	while (left <= right)
	{
		if (ps->data[mid] == d)
		{
			return mid;
		}
		else if (ps->data[mid] > d)
		{
			right = mid - 1;
		}
		else if (ps->data[mid] < d)
		{
			left = mid + 1;
		}
		return -1;
	}
}

test.c

#include"SeqList.h"

void test1()
{
	SeqList my_list;
	InitSeqList(&my_list);
	PushBack(&my_list, 1);
	PushBack(&my_list, 2);
	PushBack(&my_list, 3);
	PushBack(&my_list, 4);
	Display(&my_list);
	PopBack(&my_list);
	Display(&my_list);
	PopBack(&my_list);
	Display(&my_list);
}

void test2()
{
	SeqList my_list;
	InitSeqList(&my_list);
	PushFront(&my_list, 1);
	PushFront(&my_list, 2);
	PushFront(&my_list, 2);
	PushFront(&my_list, 4);
	PushFront(&my_list, 5);
	Display(&my_list);
	RemoveAll(&my_list, 2);
	Display(&my_list);
}

void test3()
{
	SeqList my_list;
	InitSeqList(&my_list);
	PushBack(&my_list, 1);
	PushBack(&my_list, 5);
	PushBack(&my_list, 4);
	PushBack(&my_list, 2);
	PushBack(&my_list, 3);
	Display(&my_list);
	//Insert(&my_list, 2, 4);
	Sort(&my_list);
	Display(&my_list);
}

void test4()
{
	SeqList my_list;
	int ret = 0;
	InitSeqList(&my_list);
	PushFront(&my_list, 1);
	PushFront(&my_list, 2);
	PushFront(&my_list, 3);
	PushFront(&my_list, 4);
	PushFront(&my_list, 5);
	Display(&my_list);
	//Remove(&my_list,2);
	//Reverse(&my_list);
	ret = BinarySearch(&my_list, 3);
	printf("%d\n", ret);
}

int main()
{
	test3();
	system("pause");
	return 0;
}

生成的程式視窗：

【C語言】C語言實作靜态順序表

 順序表是在計算機記憶體中以數組的形式儲存的線性表，是指用一組位址連續的存儲單元依次存儲資料元素的線性結構。線性表采用順序存儲的方式存儲就稱之為順序表。順序表是将表中的結點依次存放在計算機記憶體中一組位址連續的存儲單元中。靜态順序表能夠實作尾插，頭插，尾删，頭删，顯示，指定位置插入、指定位置删除，删除某一特定元素，删除順序表中出現的所有的特定元素，逆序，排序，二分查找等等。新手上路，大神勿噴。文中出現的錯誤歡迎大家評批指正！

c語言 資料結構 線性表 資料
上一篇: 3327順序表應用4：元素位置互換之逆置算法
下一篇: c語言實作順序表c語言實作順序表

繼續閱讀