线性表🚀
2020-05-05 本文已影响0人
你是我患得患失的梦
#include<stdio.h>
//void PrintN ( int N )
//{
// int i;
// for ( i=1; i<=N; i++ ) {
// printf("%d\n", i );
// }
// return;
//}
//void PrintN ( int N )
//{
// if ( N ) {
// PrintN( N - 1 );
// printf("%d\n", N );
// }
// return;
//}
int main()
{
int N;
scanf("%d", &N);
PrintN( N );
return 0;
}
//调用函数我们发现当N的规模达到一个比较大的数的时候用递归的函数直接罢工，而循环的函数能够正常输出，这是因为在递归调用的时候回占用的大量的空间我们计算机把可用的空间都用了但是还是不够所递归的函数就无法执行了
解决问题方法的效率跟数据的组织方式有关。
#include<stdio.h>
#include<time.h>
#include<math.h>
clock_t start, stop;
double duration; //运行时间
#define MAXN 10
#define MAXK 1e7
double f1( int n, double a[], double x);
double f2( int n, double a[], double x);
double f1(int n, double a[], double x)
{
int i;
double p = a[0];
for( i=1; i<=n; i++ )
p += (a[n] * pow(x, i));
return p;
}
double f2(int n, double a[], double x)
{
int i;
double p = a[n];
for( i=n; i>0; i-- )
p += a[n-1] + x*p;
return p;
}
int main()
{
int i;
double a[MAXN];
for( i=0; i<MAXN; i++ )
a[i] == (double)i;
start = clock();
for( i=0; i<MAXK; i++) //这里因为我们函数运行一次的时间远远没有达到计算机一次打点的时间所以我们让它多运行几次然后等捕捉到时间之后再除以循环次数就能算出一次的运行时间
f1(MAXN-1, a , 1.1);
stop = clock();
duration = ((double)(stop - start))/CLK_TCK/MAXK;
printf("ticks1 = %f\n", (double)(stop - start));
printf("duration1 = %6.2e\n", duration);
start = clock();
for( i=0; i<MAXK; i++)
f2(MAXN-1, a , 1.1);
stop = clock();
duration = ((double)(stop - start))/CLK_TCK/MAXK;
printf("ticks2 = %f\n", (double)(stop - start));
printf("duration2 = %6.2e\n", duration);
return 0;
}
/*结果
ticks1 = 14433.000000
duration1 = 1.44e-006
ticks2 = 9005.000000
duration2 = 9.01e-007
*/
解决问题方法的效率跟算法的巧妙程序有关。
什么是数据结构：
数据对象在计算机中的组织方式：
- 逻辑存储结构
- 物理存储结构
数据对象必定与一系列加在其上面的操作相关联，而完成这些操作所用的方式就是算法
抽象数据类型（Abstract Data Type）
数据类型：
- 数据对象集
- 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体的实现
- 与存放数据的机器无关
- 于数据存储的物理结构无关
- 与实现操作的算法和编程语言无关
只描述数据对象集合相关的操作集是什么，并不涉及如何做到的问题
什么是算法：
算法（Algorithm）
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定在有限步骤之后结束
- 每一条指令必须
- 有充分明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述不应该依赖于任何一种计算机语言以及具体的实现手段
什么是好的算法：
-
时间复杂度T(n)：根据算法写成的程序在执行时耗费的时间的长度
-
空间复杂度S(n)：根据算法写成的程序在执行时耗费的空间的长度
1 < log n < n < nlogn < n^2 < 2^n < n!
线性表及其实现
线性表：
由同类型数据元素构成的y有序序列的线性结构
- 表中的元素个数成为线性表的长度
- 线性表没有元素时，成为空表
- 表的起始位置成为表头，表结束的位置成为表尾
线性表的抽象数据类型描述
类型名称：线性表（List）
数据对象集：线性表是n个元素构成的有序序列
操作集：线性表L∈List，整数i表示位置，元素X∈ElementType,
线性表基本操作主要有：
void PrintL(List L); //打印线性表
List MakeEmpty(); //初始化一个空的线性表
ElementType FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
void Insert( ElementType X, int i, List L);//在位序i前面插入一个新元素X
void Delete( int i, List L);//删除指定位序i的元素
void Change( int i, ElementType x, List L);//更改指定位置的元素内容
int Find( ElementType X, List L);//在线性表中查找X第一次出现的位置
int Length( List L); //返回线性表L的长度
线性表的顺序存储实现
- 利用数组的连续存储空间顺序存放线性表的各元素
利用数组的连续存储空间 顺序存放线性表的各元素
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define MAXSIZE 100
struct Lnode {
ElementType Data[MAXSIZE];
int Last;
};
typedef struct Lnode *List;
struct Lnode Ld;
List PtrL;
void PrintL(List L); //打印线性表
List MakeEmpty(); //初始化一个空的线性表
ElementType FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
void Insert( ElementType X, int i, List L);//在位序i前面插入一个新元素X
void Delete( int i, List L);//删除指定位序i的元素
void Change( int i, ElementType x, List L);//更改指定位置的元素内容
int Find( ElementType X, List L);//在线性表中查找X第一次出现的位置
int Length( List L); //返回线性表L的长度
int main()
{
PtrL = MakeEmpty();
int i;
for( i=0; i<20; i++)
{
PtrL->Data[i] = i+1;
PtrL->Last = i;
}
PrintL(PtrL);
ElementType x;
x = FindKth(10, PtrL);
printf("x = %d\n", x);
printf("The index of x is :%d\n", Find(x, PtrL));
Insert(x, 5, PtrL);
PrintL(PtrL);
Delete(10, PtrL);
PrintL(PtrL);
Change(5, 21, PtrL);
PrintL(PtrL);
return 0;
}
void PrintL( List L)
{
int i;
printf("The List is: \n");
for( i=0; i<= L->Last; i++)
{
printf("%4d", L->Data[i]);
}
printf("\n");
return;
}
List MakeEmpty()
{
List PtrL;
PtrL = (List )malloc(sizeof(struct Lnode));
PtrL->Last = -1;
return PtrL;
}
ElementType FindKth( int K, List L)
{
if( K > L->Last )
{
printf("exceed!\n");
return 99;
} else if( L->Last == -1) {
printf("This List is empty!\n");
return -1;
}
return L->Data[K];
}
void Insert( ElementType X, int i, List L)
{
int j;
if( L->Last == MAXSIZE-1 )
{//表满
printf("This list is full!\n");
return;
}
for( j=L->Last+1; j>i; j-- )
{
L->Data[j] = L->Data[j-1];
}
L->Data[j] = X;
L->Last++;
return;
}
void Delete( int i, List L)
{
if( L->Last == -1)
{//表空
printf("This List is empty!\n");
return;
}
if( i > L->Last )
{
printf("The element is not found at this list!\n", i);
return;
}
for( i; i<L->Last; i++)
{
L->Data[i] = L->Data[i+1];
}
L->Last--;
return;
}
void Change( int i, ElementType x, List L)
{
if( L->Last == -1) {
printf("This List is empty!\n");
return;
} else if( i > L->Last ) {
printf("The element is not found at this list!\n", i);
return;
} else {
L->Data[i] = x;
return;
}
}
int Find( ElementType X, List L)
{
int i=0;
while( L->Data[i] != X && i <= L->Last )
{
i++;
}
if( i > L->Last )
return -1; //not find ElementType X
else
return i;
}
int Length( List L)
{
return L->Last;
}
- 利用链式存储来实现线性表的逻辑相邻关系
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define MAXSIZE 100
typedef struct Lnode *ptrToLnode;
struct Lnode {
ElementType Data;
ptrToLnode Next;
};
typedef ptrToLnode List;
typedef ptrToLnode Position;
List PtrL;
void PrintL(List L); //打印线性表
List MakeEmpty(); //初始化一个空的线性表
int Length( List L); //返回线性表L的长度
List FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
List Find( ElementType x, List L);//在线性表中查找X第一次出现的位置
List Insert( ElementType x, int i, List L);//在位序i前面插入一个新元素X
List Delete( int i, List L);//删除指定位序i的元素
List Change( int i, ElementType x, List L);//更改指定位置的元素内容
int main()
{
PtrL = MakeEmpty();
int i;
List p = PtrL;
for( i=0; i<20; i++)
{
if( i==0 )
{
p->Data = i+1;
p->Next = NULL;
}
else
{
List t;
t = (List )malloc(sizeof(struct Lnode));
t->Data = i+1;
t->Next = NULL;
p->Next = t;
p = p->Next;
}
}
PrintL(PtrL);
printf("Length = %d\n", Length(PtrL));
printf("Findkth(10) = %d\n", FindKth(10, PtrL)->Data);
printf("Find(12) = %d\n", Find(12, PtrL)->Data);
PtrL = Insert(99,1,PtrL);
PrintL(PtrL);
PtrL = Change(1,0,PtrL);
PrintL(PtrL);
PtrL = Delete(1,PtrL);
PrintL(PtrL);
return 0;
}
void PrintL( List L)
{
if( L == NULL )
{
printf("This List is empty!\n");
return;
} else {
List temp = L;
printf("This List is:\n");
while( temp->Next != NULL )
{
printf("%4d", temp->Data);
temp = temp->Next;
}
printf("%4d", temp->Data);
printf("\n");
return;
}
}
List MakeEmpty()
{
List L;
L = (List )malloc(sizeof(struct Lnode));
L->Next == NULL;
return L;
}
int Length( List L)
{
List T = L;
int i = 0;
while( T != NULL)
{
i++;
T = T->Next;
}
return i;
}
List FindKth(int K, List L)
{
List T = L;
int i=1;
while( i != K && T != NULL)
{
T = T->Next;
i++;
}
if( i==K )
return T;
else return NULL;
}
List Find( ElementType x, List L)
{
List T = L;
while( T != NULL && T->Data != x )
{
T = T->Next;
}
if( T->Data == x)
return T;
else return NULL;
}
List Insert( ElementType x, int i, List L)
{
if( i==1 )
{
List s;
s = (List)malloc(sizeof(struct Lnode));
s->Data = x;
s->Next = L;
return s;
} else {
int j = 1;
List T = L;
while( j != i - 1 && T != NULL)
{
T = T->Next;
j++;
}
if( T == NULL )
{
printf("not find position %d\n", i);
return L;
} else {
List s;
s = (List)malloc(sizeof(struct Lnode));
s->Data = x;
s->Next = T->Next;
T->Next = s;
return L;
}
}
}
List Delete( int i, List L)
{
if( i==1 )
{
return L->Next;
}
else {
int j=1;
List T = L;
while( j != i-1 && T != NULL)
{
T = T->Next;
j++;
}
if( T == NULL )
{
printf("not found position %d\n", i);
return L;
} else {
Position A = T->Next;
T->Next = A->Next;
free(A);
return L;
}
}
}
List Change( int i, ElementType x, List L)
{
if( i==1 )
{
L->Data = x;
return L;
}
else {
int j=1;
List T = L;
while( j != i-1 && T != NULL)
{
T = T->Next;
j++;
}
if( T == NULL )
{
printf("not found position %d\n", i);
return L;
} else {
T->Data = x;
return L;
}
}
}
广义表
- 广义表是线性表的推广
- 对于线性表而言，n个元素都是基本的单元素
- 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
广义表
typedef struct Gnode *GList;
struct Gnode {
int Tag; //标志域：0表示节点是单元素，1表示节点是广义表
union { //子表指针域SubList和单元素数字域Data复用，及公用存储空间
ElementType Data;
GList SubList;
}URegion;
Glist Next; //指向后继节点
}
广义表节点示意图
多重链表
多重链表链表中的节点可能同时隶属于多个链
- 多重链表中节点的指针域会有多个，如前面的例子中SubList和Next两个指针域
-
注意包含多个指针域的链表不一定就是多重链表，比如在双向链表不是多重链表
多重链表1
多重链表2
多重链表3
