建网站_中国造价信息网官网_百度怎么推广广告_企业管理培训课程网课免费

目录

1.1顺序表

1.1.1 顺序表特性

1.1.2 操作数组

1.1.3 添加全局变量last表示最后一个有效元素下标

1.1.4 顺序表编程实现

1.1.5 分文件编程

顺序表特点：

---

 

线性表是最基本、最简单、也是最常用的一种数据结构，可以存储逻辑关系为线性的数据。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

包含：顺序表(数组)、链表(单向链表、单向循环链表、双向链表、双向循环链表)、栈(顺序栈、链式栈)、队列（循环队列、链式队列）

逻辑结构：线性结构

存储结构：顺序存储(通过数组)或链式存储(通过指针)

特点：一对一，每个节点最多有一个前驱节点和后继节点，首节点无前驱，尾节点无后继。

1.1顺序表

顺序表存储数据的具体实现方案是：将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。

举个简单的例子，将 {1,2,3,4,5} 这些数据使用顺序表存储，数据最终的存储状态如下图所示：

1.1.1 顺序表特性

特点:内存连续，大小固定。

逻辑结构：线性结构

存储结构：顺序存储

操作：增删改查

1.1.2 操作数组

例题：

int a[100] = {1,2,3,4,5,6,7,8};

函数命名规则：

下划线法：create_empty_seqlist

小驼峰法：createEmptySeqList

大驼峰法：CreateEmptySeqList

#include <stdio.h>
#include <stdio.h>
/*  (1) 插入数组元素功能：向数组的第几个位置插数据函数：void insetIntoA(int *p,int n, int post, int data);参数：int *p: 保存数组首地址int n: 有效数据元素的个数int post: 插入元素下标int data: 数据
*/
void insertIntoA(int *p, int n, int post, int data)
{//1.把最后一个元素p[n-1]到插入位置元素p[post]向后移动一个单位for (int i = n - 1; i >= post; i--)p[i + 1] = p[i];//2.插入新元素data到指定位置p[post]p[post] = data;
}/*  (2) 遍历数组元素功能：遍历数组中的有效元素函数：void showA(int *p,int n);参数：int *p:保存数组收地址int n:有效数据元素的个数
*/
void showA(int *p, int n)
{for (int i = 0; i < n; i++)printf("%d ", p[i]);printf("\n");
}
/*  （3）删除数组中指定元素功能：删除数组中指定元素 函数：void deleteIntoA(int *p,int n, int post);参数：int *p: 保存数组首地址int n: 有效数据元素的个数int post: 删除元素下标
*/
void deleteIntoA(int *p, int n, int post)
{//从删除位置后一个元素p[post+1]到最后一个元素p[n-1]往前移动一个单位for(int i=post+1;i<n;i++)p[i-1]=p[i];
}int main(int argc, char const *argv[])
{int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};showA(a, 8);insertIntoA(a, 8, 3, 100);showA(a, 9);deleteIntoA(a,9,6);showA(a,8);return 0;
}

1.1.3 添加全局变量last表示最后一个有效元素下标

进一步优化：通过添加全局变量last表示最后一个有效元素下标，可以去掉表示有效元素个数的参数了。

#include <stdio.h>
int last = 7; //代表最后一个有效元素的下标，last=有效元素个数-1/*  功能：向数组的第几个位置插数据函数：void insetIntoA(int *p,int n, int post, int data);参数：int *p: 保存数组首地址int post: 插入元素下标int data: 数据
*/
void insertIntoA(int *p, int post, int data)
{//1.把最后一个元素p[last]到插入位置元素p[post]向后移动一个单位for (int i = last; i >= post; i--)p[i + 1] = p[i];//2.插入新元素data到指定位置p[post]p[post] = data;//3.最后一个有效元素下标加一last++;
}/*功能：遍历数组中的有效元素函数：void showA(int *p,int n);参数：int *p:保存数组收地址
*/
void showA(int *p)
{for (int i = 0; i <= last; i++)printf("%d ", p[i]);printf("\n");
}/*  功能：删除数组中指定元素 函数：void deleteIntoA(int *p,int n, int post);参数：int *p: 保存数组首地址int post: 删除元素下标
*/
void deleteIntoA(int *p, int post)
{//从删除位置后一个元素p[post+1]到最后一个元素p[n-1]往前移动一个单位for (int i = post + 1; i <= last; i++)p[i - 1] = p[i];//让最后一个有效元素下标减一last--;
}int main(int argc, char const *argv[])
{int a[100] = {1, 2, 3, 4, 5, 6, 7, 8};showA(a);insertIntoA(a, 3, 100);showA(a);deleteIntoA(a, 6);showA(a);return 0;
}

1.1.4 顺序表编程实现

封装结构体：

#define N 100
typedef int datatype;
typedef struct seqlist
{datatype data[N];int last;   //表示数组中最后一个有效元素的下标
}seqlist_t,* seqlist_p;//struct seqlist A; //相当于 seqlist_t A;
//struct seqlist *p; //相当于 seqlist_p p;
//相当于seqlist_t *p;

创空：

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define N 100
typedef int datatype;
typedef struct seqlist
{datatype data[N];int last; //表示数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;seqlist_p CreateEpSeqlist()
{//1.动态申请一块空间存放顺序表seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));if (NULL == p) //容错判断{perror("malloc err");return NULL;}//2. 对last初始化p->last = -1; //空顺序表return p;
}//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p)
{return p->last + 1 == N;
}//向顺序表的指定位置插入
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{int i;//1. 容错判断if (IsFullSeqlist(p) || post < 0 || post > p->last + 1){printf("InsertIntoSeqlist err\n");return -1; //错误返回}//2. 从最后一个下标为p->last到插入位置post元素向后移动一个单位for (i = p->last; i >= post; i--)p->data[i + 1] = p->data[i];//3. 插入数据p->data[post] = data;//4. 让last加一表示多了一个元素p->last++;return 0;
}//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p)
{for (int i = 0; i <= p->last; i++)printf("%d ", p->data[i]);printf("\n");
}//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p)
{return p->last == -1;
}//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post)
{//1. 容错判断if (IsEpSeqlist(p) || post < 0 || post > p->last){printf("DeleteIntoSeqlist err\n");return -1; //错误返回}//2. 从下标post+1到最后下标为p->last的元素向前移动一个单位for (int i = post + 1; i <= p->last; i++)p->data[i - 1] = p->data[i];//3. 让有效元素下标p->last减一p->last--;return 0;
}//清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p)
{p->last = -1; // 让last访问不到数据元素了，相当于清空
}//修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data)
{//1. 容错判断if (IsEpSeqlist(p) || post < 0 || post > p->last){perror("ChangePostSeqList err");return -1;}//2. 修改指定位置的数据p->data[post] = data;return 0;
}//查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data)
{for (int i = 0; i <= p->last; i++){if (p->data[i] == data)return i;}return -1;
}int main(int argc, char const *argv[])
{seqlist_p p = CreateEpSeqlist();printf("is empty? %d\n", IsEpSeqlist(p));InsertIntoSeqlist(p, 0, 1);InsertIntoSeqlist(p, 1, 2);InsertIntoSeqlist(p, 2, 3);InsertIntoSeqlist(p, 3, 4);ShowSeqlist(p);DeleteIntoSeqlist(p, 1);ShowSeqlist(p);// ClearSeqList(p); //清空printf("is empty? %d\n", IsEpSeqlist(p));ChangePostSeqList(p, 2, 1000);ShowSeqlist(p);printf("1000 post is:%d\n", SearchDataSeqList(p, 1000));return 0;
}

1.1.5 分文件编程

seqlist.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__#define N 100
typedef int datatype;
typedef struct seqlist
{datatype data[N];int last; //表示数组中最后一个有效元素的下标
} seqlist_t, *seqlist_p;//创建空顺序表
seqlist_p CreateEpSeqlist();//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p);//向顺序表的指定位置插入
int InsertIntoSeqlist(seqlist_p p, int post, int data);//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p);//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p);//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post);//清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p);//修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data);//查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data);#endif

seqlist.c

#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"//创建空顺序表
seqlist_p CreateEpSeqlist()
{//1.动态申请一块空间存放顺序表seqlist_p p = (seqlist_p)malloc(sizeof(seqlist_t));if (NULL == p) //容错判断{perror("malloc err");return NULL;}//2. 对last初始化p->last = -1; //空顺序表return p;
}//判断顺序表是否为满，满返回1,未满返回0
int IsFullSeqlist(seqlist_p p)
{return p->last + 1 == N;
}//向顺序表的指定位置插入
int InsertIntoSeqlist(seqlist_p p, int post, int data)
{int i;//1. 容错判断if (IsFullSeqlist(p) || post < 0 || post > p->last + 1){printf("InsertIntoSeqlist err\n");return -1; //错误返回}//2. 从最后一个下标为p->last到插入位置post元素向后移动一个单位for (i = p->last; i >= post; i--)p->data[i + 1] = p->data[i];//3. 插入数据p->data[post] = data;//4. 让last加一表示多了一个元素p->last++;return 0;
}//遍历顺序表sequence顺序list表
void ShowSeqlist(seqlist_p p)
{for (int i = 0; i <= p->last; i++)printf("%d ", p->data[i]);printf("\n");
}//判断顺序表是否为空，为空返回1，不为空返回0
int IsEpSeqlist(seqlist_p p)
{return p->last == -1;
}//删除顺序表中指定位置的数据，post为删除位置
int DeleteIntoSeqlist(seqlist_p p, int post)
{//1. 容错判断if (IsEpSeqlist(p) || post < 0 || post > p->last){printf("DeleteIntoSeqlist err\n");return -1; //错误返回}//2. 从下标post+1到最后下标为p->last的元素向前移动一个单位for (int i = post + 1; i <= p->last; i++)p->data[i - 1] = p->data[i];//3. 让有效元素下标p->last减一p->last--;return 0;
}//清空顺序表（清空：访问不到，但是内存中还有。销毁：内存清空）
void ClearSeqList(seqlist_p p)
{p->last = -1; // 让last访问不到数据元素了，相当于清空
}//修改指定位置上数据
int ChangePostSeqList(seqlist_p p, int post, int data)
{//1. 容错判断if (IsEpSeqlist(p) || post < 0 || post > p->last){perror("ChangePostSeqList err");return -1;}//2. 修改指定位置的数据p->data[post] = data;return 0;
}//查找指定数据出现的位置,返回下标，未找到返回-1
int SearchDataSeqList(seqlist_p p, int data)
{for (int i = 0; i <= p->last; i++){if (p->data[i] == data)return i;}return -1;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "seqlist.h"int main(int argc, char const *argv[])
{seqlist_p p = CreateEpSeqlist();printf("is empty? %d\n", IsEpSeqlist(p));InsertIntoSeqlist(p, 0, 1);InsertIntoSeqlist(p, 1, 2);InsertIntoSeqlist(p, 2, 3);InsertIntoSeqlist(p, 3, 4);ShowSeqlist(p);DeleteIntoSeqlist(p, 1);ShowSeqlist(p);// ClearSeqList(p); //清空printf("is empty? %d\n", IsEpSeqlist(p));ChangePostSeqList(p, 2, 1000);ShowSeqlist(p);printf("1000 post is:%d\n", SearchDataSeqList(p, 1000));return 0;
}

makefile

CC=gcc
GFLAGS=-c -g -Wall
OBJS=seqlist.o main.oseqlist:$(OBJS)$(CC) $^ -o $@
%.o:%.c$(CC) $(GFLAGS) $< -o $@
.PHONY:clean
clean:$(RM) seqlist *.o

顺序表特点：

1. 顺序的内存空间连续

2. 长度固定

3. 查和改效率高，插入和删除涉及到元素的移动所以效率低。