数据结构02(顺序表数组实现，链式表，完整代码实现)数据结构之顺序表

80 阅读 0 评论 53 点赞

我是靠谱客的博主淡淡凉面，最近开发中收集的这篇文章主要介绍数据结构02(顺序表数组实现，链式表，完整代码实现)数据结构之顺序表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数据结构之顺序表

一、顺序表的介绍

顺序表是在计算机内存中以数组的形式保存的线性表

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构结构的线性表通常称为顺序表。

顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

二、顺序表的要求

数组实现：

顺序表的数据项：存储元素的连续内存首地址、表的容量、当前元素的数量

支持的运算：创建、销毁、清空、插入、删除、访问、查询、修改、排序、遍历

链表实现：

元素(结点)的数据项为：1、数据域：可以是任何类型的若干个数据项。2、指针域：指向下一个结点。

其中带有头节点和不带有头节点的链表实现存在差异：

不带头结点的单链表：
第一个结点的数据域存储有效数据
缺点：添加、删除结点时，可能修改指向第一个结点的指针，参数需要使用二级指针，才能更改指针的指向，比较麻烦

带头结点的单链表：
第一个结点的数据域不存储有效元素，仅仅只是使用它的指针域永远指向链表的第一个数据有效的结点，可以使插入、删除等操作变得简便，缺点是浪费了一块内存

三、代码实现

1）顺序表数组实现

/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#define TYPE int
// 设计顺序表结构
typedef struct Array{
TYPE* ptr;	//存储元素的内存首地址
size_t cal;	//表的容量
size_t cnt;	//已存储元素的数量
}Array;
//创建
Array* create_array(size_t cal);
//销毁
void destory_array(Array* arr);
//清空
void clean_array(Array* arr);
//插入
bool insert_array(Array* arr,int index,TYPE val);
//删除
bool delete_array(Array* arr,size_t index);
//访问
bool access_array(Array* arr,size_t index,TYPE* val);
//查询
int query_array(Array* arr,TYPE val);
//修改
bool modify_array(Array* arr,size_t index,TYPE val);
//排序
void sort_array(Array* arr);
//遍历
void show_array(Array* arr);
Array* create_array(size_t cal)
{
//分配顺序表结构的内存
Array* arr=(Array*)malloc(sizeof(Array));
if(arr == NULL)
{
return NULL;
}
//分配储存元素的内存
arr->ptr = (TYPE*)malloc(sizeof(TYPE)*cal);
arr->cal = cal;
arr->cnt = 0;
return arr;
}
void destory_array(Array* arr)
{
free(arr->ptr);
free(arr);
}
void clean_array(Array* arr)
{
arr->cnt = 0;
}
bool insert_array(Array* arr,int index,TYPE val)
{
//判断表是否满
if(arr->cal <= arr->cnt)	return false;
if(index > arr->cnt || index < 0)	return false;
/*
for(int i=arr->cnt; i>index; i--)
{
arr->ptr[i] = arr->ptr[i-1];
}
*/
memmove(arr->ptr+index+1,arr->ptr+index,(arr->cnt-index)*sizeof(TYPE));
arr->ptr[index] = val;
arr->cnt++;
return true;
}
bool delete_array(Array* arr,size_t index)
{
if(index >= arr->cnt)	return false;
/*
for(int i=index;i<arr->cnt-1;i++)
{
arr->ptr[i] = arr->ptr[i+1];
}
*/
memmove(arr->ptr+index,arr->ptr+index+1,sizeof(TYPE)*arr->cnt-index-1);
arr->cnt--;
return true;
}
bool access_array(Array* arr,size_t index,TYPE* val)
{
if(index >= arr->cnt)	return false;
*val = arr->ptr[index];
return true;
}
int query_array(Array* arr,TYPE val)
{
for(int i=0; i<arr->cnt; i++)
{
if(arr->ptr[i] == val)
{
return i;
}
}
return -1;
}
bool modify_array(Array* arr,size_t index,TYPE val)
{
if(index >= arr->cnt)	return false;
arr->ptr[index] = val;
return true;
}
void sort_array(Array* arr)
{
for(int i=0; i<arr->cnt-1; i++)
{
for(int j=i+1; j<arr->cnt;j++)
{
if(arr->ptr[i]>arr->ptr[j])
{
TYPE temp;
temp = arr->ptr[i];
arr->ptr[i] = arr->ptr[j];
arr->ptr[j] = temp;
}
}
}
}
void show_array(Array* arr)
{
if(arr == NULL)	return;
for(int i=0; i<arr->cnt;i++)
{
printf("%d ",arr->ptr[i]);
}
printf("n");
}
int main(int argc,const char* argv[])
{
//这里写测试代码，我就不写了
return 0;
}

2）链式表不带头结点实现

/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
//设计链表中节点的类型
typedef struct Node{
TYPE data;
//节点数据域
struct Node* next;	//节点指针域
}Node;
//创建节点
Node* create_node(TYPE data);
//头添加
void add_head_list(Node** head,int val);
//按值删除
bool del_value_list(Node** head,TYPE data);
//按下标位置删除
bool del_index_list(Node** head,size_t index);
//排序
void sort_list(Node* head);
//遍历
void show_list(Node* head);
//访问
bool access_list(Node* head,int index,TYPE* val);
Node* create_node(TYPE data)
{
//分配节点所需要的内存
Node* node = (Node* )malloc(sizeof(Node));
node->data = data;
node->next = NULL;
}
void add_head_list(Node** head,int val)
{
Node* node = create_node(val);
node->next = *head;
*head = node;
}
bool del_value_list(Node** head,TYPE data)
{
if(data == (*head)->data)
{
Node* temp = *head;
*head = (*head)->next;
free(temp);
return true;
}
for(Node* n=*head; n->next!=NULL; n=n->next)
{
if(n->next->data == data)
{
Node* temp = n->next;
n->next = temp->next;
free(temp);
return true;
}
}
return false;
}
bool del_index_list(Node** head,size_t index)
{
if(index == 0)
{
Node* node = *head;
*head = node->next;
free(node);
return true;
}
Node* pre=*head;
for(int i=0;i<index-1;i++)
{
pre = pre->next;
if(pre == NULL)
{
return false;
}
}
Node* temp = pre->next;
pre->next = temp->next;
free(temp);
return true;
}
void sort_list(Node* head)
{
for(Node* i=head; i->next!=NULL; i=i->next)
{
for(Node* j=i->next;j!=NULL;j=j->next)
{
if(i->data > j->data)
{
TYPE temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}
}
void show_list(Node* head)
{
for(Node* n=head; n!=NULL; n=n->next)
{
printf("%d ",n->data);
}
printf("n");
}
bool access_list(Node* head,int index,TYPE* val)
{
Node* node = head;
for(int i=0; i<index; i++)
{
node = node->next;
if(node == NULL)	return false;
}
*val = node->data;
return true;
}
int main(int argc,const char* argv[])
{
//这里写测试代码
return 0;
}

3）链式表带头结点实现（推荐）

/************************************
> 作者：杭电羊皮卷
> weixin:QQ2997675141
************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TYPE int
//设计链表中节点的类型
typedef struct Node{
TYPE data;
//节点数据域
struct Node* next;	//节点指针域
}Node;
//创建节点
Node* create_node(TYPE data);
//头插法插入节点
void add_head_list(Node* head,TYPE val);
//尾插法插入节点
void add_tail_list(Node* head,TYPE val);
//按值删除
bool del_value_list(Node* head,TYPE val);
//按下标位置删除
bool del_index_list(Node* head,size_t index);
//在指定位置插入（排除头和尾）
bool insert_list(Node* head,size_t index,TYPE val);
//修改
bool modify_list(Node* head,TYPE old,TYPE new);
//访问
bool access_list(Node* head,size_t index,TYPE* val);
//按值查找
int query_list(Node* head,TYPE val);
//啥也不是排序法
void sort_list(Node* head);
//遍历
void show_list(Node* head);
Node* create_node(TYPE data)
{
//分配节点所需要的内存
Node* node = (Node* )malloc(sizeof(Node));
node->data = data;
node->next = NULL;
}
void add_head_list(Node* head,TYPE val)
{
Node* node = create_node(val);
node->next = head->next;
head->next = node;
}
void add_tail_list(Node* head,TYPE val)
{
while(head->next != NULL)
{
head = head->next;
}
Node* node = create_node(val);
head->next = node;
}
bool del_value_list(Node* head,TYPE val)
{
while(head->next != NULL)
{
if(head->next->data == val)
{
Node* temp;
temp = head->next;
head->next = temp->next;
free(temp);
return true;
}
}
return false;
}
bool del_index_list(Node* head,size_t index)
{
Node* n = head;
if(NULL == n->next)	return false;
for(int i=0; i<index; i++)
{
if(NULL == n->next)	return false;
n=n->next;
}
if(NULL == n->next)	return false;
Node* temp = n->next;
n->next = temp->next;
free(temp);
return true;
}
bool insert_list(Node* head,size_t index,TYPE val)
{
Node* n = head;
if(n->next == NULL || index == 0)	return false;
for(int i=0; i<index; i++)
{
n = n->next;
if(NULL == n->next)	return false;
}
Node* node = create_node(val);
node->next = n->next;
n->next = node;
return true;
}
bool modify_list(Node* head,TYPE old,TYPE new)
{
for(Node* n=head; NULL!=n; n=n->next)
{
if(n->data == old)
{
n->data = new;
return true;
}
}
return false;
}
bool access_list(Node* head,size_t index,TYPE* val)
{
Node* n = head->next;
if(NULL == n)	return false;
for(int i=0; i<index; i++)
{
n = n->next;
if(NULL == n)	return false;
}
*val = n->data;
return true;
}
int query_list(Node* head,TYPE val)
{
Node* n = head->next;
for(int i=0; NULL!=n; i++)
{
if(n->data == val)	return i;
n = n->next;
}
return -1;
}
void sort_list(Node* head)
{
for(Node* i=head->next; i->next!=NULL; i=i->next)
{
for(Node* j=i->next; j!=NULL; j=j->next)
{
if(i->data > j->data)
{
TYPE t= j->data;
j->data = i->data;
i->data = t;
}
}
}
}
void show_list(Node* head)
{
for(Node* node = head->next; node!=NULL; node=node->next)
{
printf("%d ",node->data);
}
printf("n");
}
int main()
{
//head就是带头节点链表的头节点
//head->next永远指向第一个有效数据的节点
Node* head = create_node(0);
//这里写测试代码
return 0;
}