顺序链表-白红宇

顺序链表

阅读量：6007 次

发布时间：2019-06-20

本文共 5459 字，大约阅读时间需要 18 分钟。

学习链表是为了更好的学习c++；顺序链表又是最简单的链表。顺序链表在实现的时候有些需要注意的事情。

实现顺序链表初始化，尾部插入，尾部删除，头部插入，头部删除，选择位置插入，查找，删除某个位置上的数，删除一个。

一.首先让我们将定义一个结构体

    typedef struct SeqList    {    	DataType array[MAX_SIZE];    	size_t size;    }SeqList;

可以发现我在上面使用了宏和typedef。

    typedef int DataType;    #define MAX_SIZE 5

好处：1.需要将数组的大小改变的时候，直接改变宏的地方。

2.可以随意改变数据类型。

二.让我们来写出来上面函数的声明

    void InitList(SeqList *pSeq);    void PushBack(SeqList *pSeq,DataType x);    void PopBack(SeqList *pSeq);    void PrintfList(SeqList *pSeq);        void PushFront(SeqList *pSeq, DataType x);    void PopFront(SeqList *pSeq);        void Insert(SeqList *pSeq, size_t pos, DataType x);        int Find(SeqList *pSeq, DataType x);    void Erase(SeqList *pSeq, size_t pos);    void Remove(SeqList *pSeq, DataType x);    void RemoveAll(SeqList *pSeq, DataType x);

1.声明为指针

如果声明为结构体变量，那么在传参的时候会考进来一份临时拷贝，改掉的并不是真正的结构体数组中的值。可以用一个小程序来验证。

    #include
     
              void fun(int a,int b)    {    	int z = a;    	 a = b;    	 b = z;    	printf("%d %d\n", a, b);    }        int main()    {    	int a = 10;    	int b = 20;    	fun(a, b);    	printf("%d %d\n", a, b);    	system("pause");    	return 0;    }

为什么两个打印的结果不一样？

直接说原因，因为传参的时候考了两份临时变量给了fun函数导致在fun函数内部更改的不是内存中保存a和b的值。同样的道理，在顺序链表中，就会存在这样的问题。那么，声明为指针，传参的时候将地址传过来，在函数的内部直接操作内存就是一种很方便的方法。

二.实现函数

1.初始化

    void InitList(SeqList* pSeq)    {    	assert(pSeq);    	memset(pSeq->array, 0, sizeof(DataType)*MAX_SIZE);    	pSeq->size = 0;    }

2.尾部插入

        void PushBack(SeqList* pSeq, DataType x)//尾插    {    	assert(pSeq);    	if (pSeq->size >= MAX_SIZE)    	{    		printf("full\n");    		return;    	}    	pSeq->array[pSeq->size] = x;    	pSeq->size++;    	//Insert(pSeq, pSeq->size, x);    }

3.尾部删除

        void PopBack(SeqList* pSeq)//尾删    {    	assert(pSeq);    	if (pSeq->size <= 0)    	{    		printf("empty\n");    		return;    	}    	pSeq->size--;    }

4.头部插入

    void PushFront(SeqList *pSeq, DataType x)//头插    {        assert(pSeq);        int begin = pSeq->size - 1;        if (pSeq->size >= MAX_SIZE)    {       printf("full\n");       return;    }        for (; begin >= 0; --begin)    {        pSeq->array[begin+1] = pSeq->array[begin];    }        pSeq->array[0] = x;       ++pSeq->size;    }

5.头部删除

    void PopFront(SeqList *pSeq)//头删    {     assert(pSeq);    int begin = 1;    if (pSeq->size <= 0)    {    printf("empty\n");    return;    }    int i = pSeq->size;    for (; begin < pSeq->size; ++begin)    {    pSeq->array[begin-1] = pSeq->array[begin];    }    pSeq->size--;    }

6.选择位置插入（两种写法）

        void Insert(SeqList *pSeq, size_t pos, DataType x)    {    	//[]    //	assert(pSeq);    //	assert(pos <= pSeq->size);    //	int begin = pSeq->size - 1;    //	if (pSeq->size >= MAX_SIZE)    //	{    //		printf("full\n");    //		return;    //	}    //	for (; begin >= (int)pos; --begin)    //	{    //		pSeq->array[begin + 1] = pSeq->array[begin];    //	}    //	pSeq->array[pos] = x;    //	++pSeq->size;    //        	//(]    	assert(pSeq);    	assert(pos <= pSeq->size);    	int begin = pSeq->size;    	if (pSeq->size >= MAX_SIZE)    	{    		printf("full\n");    		return;    	}    	for (; begin > pos; --begin)    	{    		pSeq->array[begin] = pSeq->array[begin - 1];    	}    	pSeq->array[pos] = x;    	++pSeq->size;    }

7.查找

        int Find(SeqList *pSeq, DataType x)    {    	assert(pSeq);    	int i = 0;    	for (; i < pSeq->size; ++i)    	{    		if (pSeq->array[i] == x)    		{    			return i;    		}    	}    	return -1;    }

8.删除某个位置上的数

        void Erase(SeqList *pSeq, size_t pos)//删除某个位置的数据    {    	assert(pSeq);    	assert(pos <= pSeq->size);    	int begin = pos+1;    	for (; begin <= pSeq->size; ++begin)    	{    		pSeq->array[begin - 1] = pSeq->array[begin];    	}    	--pSeq->size;    }

9.打印链表

        void PrintfList(SeqList* pSeq)//打印链表    {    	assert(pSeq);    	int i = 0;    	for (i = 0; i < pSeq->size; i++)    	{    		printf("%d ", pSeq->array[i]);    	}    	printf("\n");    }

10.写函数需要注意的问题

1）.函数的参数的有效性检查

2）.边界条件

3）.实现逻辑

11.×××提升的问题在实现PopBack()函数时直接调用Insert()函数时候要尤其注意这个问题。

三.单元测试

        //InitList()/PushBack()/PopBack()    void test1()    {    	SeqList seq;        	InitList(&seq);    	    	PushBack(&seq, 1);    	PushBack(&seq, 2);    	PushBack(&seq, 3);    	PushBack(&seq, 4);        PrintfList(&seq);    	PopBack(&seq);    	PrintfList(&seq);    }           //InitList()/PushFront()/PopFront()    void test2()    {    	SeqList seq;    	InitList(&seq);    	PushBack(&seq, 1);    	PushBack(&seq, 2);    	PushBack(&seq, 3);    	PushBack(&seq, 4);    	PrintfList(&seq);        	PushFront(&seq,0);    	PushFront(&seq, -1);    	PrintfList(&seq);        	PopFront(&seq);    	PrintfList(&seq);        }        void test3()    {    	SeqList seq;    	InitList(&seq);    	PushBack(&seq, 1);    	PushBack(&seq, 2);    	PushBack(&seq, 4);    	PushBack(&seq, 5);        	Insert(&seq, 2, 3);    	Insert(&seq, 2, 3);    	PrintfList(&seq);    }    void test4()    {    	SeqList seq;    	InitList(&seq);    	PushBack(&seq, 1);    	PushBack(&seq, 2);    	PushBack(&seq, 2);    	PushBack(&seq, 3);    	PushBack(&seq, 4);        	/*int ret = Find(&seq, 2);    	printf("%d\n", ret);    	Erase(&seq, 1);    	PrintfList(&seq);*/        	//Remove(&seq, 2);        	RemoveAll(&seq, 2);    	PrintfList(&seq);    }    int main()    {    	test4();    	system("pause");    	return 0;    }

写大型项目的时候，单元测试是非常重要的，可以在实际开发中，避免问题的出现，并且易于定位问题，为调试修正bug提供线索。

以上就是本人在学习过程中的一些经验总结。当然，本人能力有限，难免会有纰漏，希望大家可以指正。

转载于:https://blog.51cto.com/10799170/1727318

你可能感兴趣的文章