C语言实现动态顺序表

布满荆棘的人生 2022-10-01 00:40 186阅读 0赞

**C语言实现静态顺序表：[http://blog.csdn.net/qq\_34021920/article/details/76222788][http_blog.csdn.net_qq_34021920_article_details_76222788]**

来看看动态的顺序表实现：

**1.seqlist.h**

#define _CRT_SECURE_NO_WARNINGS 1
    
    #ifndef __SEQLIST_H__
    #define __SEQLIST_H__
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include  <assert.h>
    
    typedef int DataType;
    
    #define DEFAULT_SZ 3
    #define INC_SZ 2
    
    typedef struct SeqList
    {
    	DataType *data;
    	int sz;
    	int capacity;
    }SeqList,*pSeqList;
    
    void InitSeqList(pSeqList pList);
    void PushBack(pSeqList pList,DataType d);
    void PopBack(pSeqList pList);
    void PushFront(pSeqList pList, DataType d);
    void PopFront(pSeqList pList);
    int Find(pSeqList pList, DataType d);
    void Remove(pSeqList pList, DataType d);
    void RemoveAll(pSeqList pList, DataType d);
    void BubbleSort(pSeqList pList);
    int BinarySearch(pSeqList pList, DataType d);
    void PrintfSeqList(pSeqList pList);
    void Insert(pSeqList pList, int pos, DataType d);
    void ReverseList(pSeqList pList);
    void DestroySeqList(pSeqList pList);
    
    
    
    
    #endif//__SEQLIST_H__

2.seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include "seqlist.h"
    
    void InitSeqList(pSeqList pList)
    {
    	pList->sz = 0;
    	pList->data = (DataType*)malloc(sizeof(DataType)*DEFAULT_SZ);
    	if (pList->data == NULL)
    	{
    		perror("malloc");
    		return;
    	}
    	memset(pList->data, 0, sizeof(DataType)*DEFAULT_SZ);
    }
    void CheckCapacity(pSeqList pList)
    {
    	assert(pList);
    	if (pList->sz == pList->capacity)
    	{
    		DataType*ret = (DataType*)realloc(pList->data, sizeof(DataType)*(pList->capacity + INC_SZ));
    		if (ret == NULL)
    		{
    			perror("realloc");
    		}
    		pList->data = ret;
    		pList->capacity += INC_SZ;
    
    	}
    }
    void PushBack(pSeqList pList, DataType d)
    {
    	assert(pList);
    	if (pList->sz == pList->capacity)
    	{
    		CheckCapacity(pList);
    	}
    	pList->data[pList->sz] = d;
    	pList->sz++;
    }
    void PopBack(pSeqList pList)
    {
    	int i = 0;
    	assert(pList);
    	if (pList->sz == 0)
    	{
    		printf("顺序表为空:<");
    		return;
    	}
    	pList->sz--;
    }
    void PushFront(pSeqList pList, DataType d)
    {
    	int i = 0;
    	assert(pList);
    	if (pList->sz == pList->capacity)
    	{
    		CheckCapacity(pList);
    	}
    	for (i = pList->sz; i >= 1; i--)
    	{
    		pList->data[i] = pList->data[i - 1];
    	}
    	pList->data[0] = d;
    	pList->sz++;
    }
    void PopFront(pSeqList pList)
    {
    	int i = 0;
    	assert(pList);
    	for (i = 0; i < pList->sz; i++)
    	{
    		pList->data[i] = pList->data[i + 1];
    	}
    	pList->sz--;
    }
    int Find(pSeqList pList, DataType d)
    {
    	int i = 0;
    	assert(pList);
    	while (i < pList->sz)
    	{
    		if (pList->data[i] == d)
    		{
    			return i;
    		}
    		else
    		{
    			i++;
    		}
    	}
    	return -1;
    }
    void Remove(pSeqList pList, DataType d)
    {
    	int i = 0;
    	int pos = 0;
    	assert(pList);
    	while (pList->data[pos=Find(pList,d)]==d)
    	{
    		for (i = pos; i < pList->sz-1; i++)
    		{
    			pList->data[i] = pList->data[i + 1];
    		}
    		pList->sz--;
    	}
    }
    void RemoveAll(pSeqList pList, DataType d)
    {
    	int i = 0;
    	int pos = 0;
    	assert(pList);
    	while ((pos = Find(pList, d)) != -1)
    	{
    		for (i = pos; i < pList->sz - 1; i++)
    		{
    			pList->data[i] = pList->data[i + 1];
    		}
    		pList->sz--;
    	}
    }
    void BubbleSort(pSeqList pList)
    {
    	int i = 0;
    	assert(pList);
    	for (i = 0; i < pList->sz - 1; i++)
    	{
    		int j = 0;
    		for (j = 0; j < pList->sz - i - 1; j++)
    		{
    			if (pList->data[j]>pList->data[j + 1])
    			{
    				DataType tmp = pList->data[j];
    				pList->data[j] = pList->data[j + 1];
    				pList->data[j + 1] = tmp;
    			}
    		}
    	}
    }
    int BinarySearch(pSeqList pList, DataType d)
    {
    	int left = 0;
    	int right = pList->sz - 1;
    	assert(pList);
    	while (left <= right)
    	{
    		int mid = left - ((left - right) >> 1);
    		if (d > pList->data[mid])
    		{
    			left = mid + 1;
    		}
    		else if (d < pList->data[mid])
    		{
    			right = mid - 1;
    		}
    		else
    			return mid;
    	}
    	return -1;
    }
    void PrintfSeqList(pSeqList pList)
    {
    	int i = 0;
    	for (i = 0; i < pList->sz; i++)
    	{
    		printf("%d ", pList->data[i]);
    	}
    }
    void Insert(pSeqList pList, int pos, DataType d)
    {
    	int i = 0;
    	if (pList->sz == pList->capacity)
    	{
    		CheckCapacity(pList);
    	}
    	for (i = pList->sz - 1; i >= pos; i--)
    	{
    		pList->data[i + 1] = pList->data[i];
    	}
    	pList->data[pos] = d;
    	pList->sz++;
    }
    void ReverseList(pSeqList pList)
    {
    	int left = 0;
    	int right = pList->sz - 1;
    	assert(pList);
    	while (left < right)
    	{
    		DataType tmp = pList->data[left];
    		pList->data[left] = pList->data[right];
    		pList->data[right] = tmp;
    		left++;
    		right--;
    	}
    }
    void DestroySeqList(pSeqList pList)
    {
    	free(pList->data);
    	pList->data = NULL;
    }

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1
    #include "seqlist.h"
    
    //void Test()
    //{
    //	SeqList *List;
    //	InitSeqList(&List);
    //	PushBack(&List, 1);
    //	PushBack(&List, 2);
    //	PushBack(&List, 3);
    //	PushBack(&List, 4);
    //	PushBack(&List, 5);
    //	PopBack(&List);
    //	printf("%d ", Find(&List, 2));
    //	PrintfSeqList(&List);
    //}
    
    void Test2()
    {
    	SeqList List;
    	InitSeqList(&List);
    	PushBack(&List, 1);
    	PushBack(&List, 2);
    	PushBack(&List, 3);
    	PushBack(&List, 4);
    	PushBack(&List, 5);
    	PushFront(&List, 5);
    	PushFront(&List, 2);
    	PushFront(&List, 3);
    	//PopFront(&List);
    	RemoveAll(&List, 5);
    	//BubbleSort(&List);
    	//BinarySearch(&List, 3);
    	PrintfSeqList(&List);
    }
    int main()
    {
    	Test2();
    	system("pause\n");
    	return 0;
    }

[http_blog.csdn.net_qq_34021920_article_details_76222788]: http://blog.csdn.net/qq_34021920/article/details/76222788