数据结构初体验——笔记整理#1线性表

c实现一个存储int数据的列表

//列表体定义 typedef int Position;//自定义类型，用以表示列表中最后一个有效元素的位置 //typedef int ElementType;//定义数据类型，此处以int型为例，可自行定义为任何类型 typedef struct LNode //定义结构体 { ElementType Data[MAX_SIZE];//数据存储表 Position Last;//最后有一个有效元素的位置 } *List;//定义头指针 //列表操作方法定义 //**初始化方法 List makeEmpty()//初始化一个空列表 { List l;//定义头指针 l = (list)malloc(sizeof(LNode));//为列表分配内存空间 l->Last = -1;//空列表数据为空，有效元素位置设为-1 return l；//返回头指针 } //**查找元素位置 Position find(List l,ElementType x) { Position i = 0;//从第一个元素开始遍历 //此处可插入列表是否空判断 /* if(l->Last == -1)//若列表为空，结束 { return NULL; } */ while(i <= l->Last && l->Data == x)//遍历完或找到指定元素时结束遍历 { i++; } if(i > l->Last) { return NULL;//若为找到元素，返回NULL } else { return i;//若找到元素，返回其位置 } } //**插入元素 bool insert(List l,ElementType x,Position p)//在列表中p位置插入一个元素 { Position i; if(l->Last == MAX_SIZE - 1)//插入前判断列表是否满 { print("列表满"); return false; } if(p < 0 || p > l->Last + 1)//检测插入位置合法性，列表为连续排列的元素，不可跳跃 { print("位置非法"); return false; } for(i = l->Last; l >= p; i--)//遍历列表，移动元素，空出插入位置，列表向后增长，因此又后向前逐个后移，直到位置p { l->Data[i+1] = l->Data[i]; } l->Data[p] = x; l->Last++;//元素个数增加一 return true; } //**删除元素 bool delete(List l,Position p) { Position i; if(p < 0 || p > l->Last)//检查位置合法性 { print("位置不合法") } for(i = p + 1; i <= l->Last; i++)//将元素由后向前移动，即可覆盖指定元素，实现删除 { l->Data[i-1] = l->Data[i]; } l->Last--;//元素减一 }

链表

c实现一个存储int型数据的单向链表

typedef struct LNode *PtrToNode;//定义节点指针 typedef int ElementType;//此处以int为例 struct LNode//定义节点结构体 { ElementType Data;//存储的数据 PrtToNode Next;//指向下一个节点的指针 }; typedef PrtToNode Position;//定义节点位置指针 typedef PrtToNode List;//定义链表头指针 //其实，上面的和下面的定义是一样的， 之所以那么麻烦是为了更详细解释链表的不同部分，比如头节点和头指针,所以实现操作方法的时候我们依然以上面的为标准 /* typedef struct LNode *List;//定义节点指针 typedef int ElementType;//此处以int为例 struct LNode//定义节点结构体 { ElementType Data;//存储的数据 List Next;//指向下一个节点的指针 }; */ //**查找 Position find(Lsit l,Elementype x) { Position p = l;//指向链表第一个节点 while( p && p->Data == x)//遍历列表直到找到指定元素或遍历结束 { p = p->Next; } if(p)//如果找到指定元素， 即p不为NULL { return p; } else { return NULL; } } //**插入（带头节点） bool insert(List l,ElementType x,Position p) { Position temp,pre; //从头结点开始遍历链表，直到找到指定节点的前一个节点或遍历至结束 for(pre = l; pre && pre->Next != p;pre = pre->Next); /*用while实现 pre = l; while(pre && pre->Next != p) { pre = pre->Next; } */ if(pre == NULL)//未找到节点 { print("插入位置错误"); } else { temp = (Position)malloc(sizeof(LNode));//申请内存建立临时节点 temp->Data = x;//存储数据 temp->Next = p;//接入链表 pre->Next = temp; return true; } } //** 删除（带头节点） bool delete(List l, Position p) { Position pre; for(pre = l; pre && pre->Next != p;pre = pre->Next); //此处效果同上 if(pre == NULL || p == NULL)//若未找到节点 { print("位置参数错误"); return false; } else { pre->Next = p->Next; free(p);//释放p位置的节点的内存 return true; } }