1、顺序表
//
// DS01_sqlist.c
// MacC_Learn01
//
// Created by Remoo on 2022/9/6.
//
// Xcode Dev
//
#include <stdio.h>
#include <stdlib.h>
#define INITSIZE 10
typedef struct
{
int *data;
int length;
int listsize;
}sqlist;//表头
void initlist(sqlist *L);
int getlen(sqlist *L);
int getelem(sqlist *L,int i, int *e);
void list(sqlist *L);
int insert(sqlist *L,int i,int x);
int SeqListErase(sqlist* sl, int pos);
int main(void)
{
sqlist sq_list;
int x;
int *elem=(int *)malloc(sizeof(int));
initlist(&sq_list);
//此时sq_list的data已经存储了malloc出来的内存首地址
printf("input datas(-1:end):");
scanf("%d",&x);
int i=1;
while(x!=-1)
{
insert(&sq_list,i,x); /* 插入 */
i++;
scanf("%d",&x);
}
printf("目前顺序表元素如下:\n");
list(&sq_list); /* 输出顺序表 */
int index,x0;
printf("在第几位序插入什么元素:\n");
scanf("%d %d",&index,&x0);
if(insert(&sq_list,index,x0))
list(&sq_list);
else
printf("插入失败!");
printf("取第几个元素:\n");
int n;
scanf("%d",&n);
if(getelem(&sq_list,n,elem))
printf("取出的元素是:%d\n",*elem);
else
printf("取出失败!");
printf("删除第几个元素:\n");
int d;
scanf("%d",&d);
if(SeqListErase(&sq_list,d))
list(&sq_list);
else
printf("删除失败!");
free(sq_list.data);
free(elem);
return 0;
}
/* 1.初始化操作(创建一个空的顺序表L) */
void initlist(sqlist *L)
{
L->data=(int *)malloc(sizeof(int)*INITSIZE);/* 申请存储空间*/
L->length=0; /* 初始长度为0 */
L->listsize=INITSIZE; /* 容量为初始量 */
}
/* 2. 求表长操作 */
int getlen(sqlist *L)
{return(L->length);}
/* 3. 取元素操作 */
int getelem(sqlist *L,int i, int *e)
{
if(i<1||i>L->length) return 0;
*e = L->data[i-1];
return 1;
}
/* 4.输出操作(输出顺序表L的各数据元素值) */
void list(sqlist *L)
{
int i;
for(i=0;i<L->length;i++)
printf("%5d ",L->data[i]);
printf("\n");
}
/* 5. 插入操作(在顺序表L中的第i个位序上插入一个值为x的数据元素) */
int insert(sqlist *L,int i,int x)
{
int j;
if(i<1||i>L->length+1) return 0; // 参数i不合理,返回0
if(L->length==L->listsize) // 存储空间不够,增加一个存储空间
{
L->data=(int *)realloc(L->data,(L->listsize+1)*sizeof(int));
L->listsize++; // 增加一个存储空间长度
}
for(j=L->length-1;j>=i-1;j--)
L->data[j+1]=L->data[j]; // 将序号为i及之后的数据元素后移一位
L->data[i-1]=x; // 在序号i处放入x
L->length++; // 顺序表长度增1
return 1; // 插入成功,返回1
}
int SeqListErase(sqlist* sl, int pos){
if(pos > sl->length)return 0;
for (int i = pos; i < sl->length; i++){
sl->data[i - 1] = sl->data[i];
}
sl->length--;
return 1;
}
2、单向链表
//
// DS002_LNode.c
// DataStructure
//
// Created by Remoo on 2022/9/17.
//
// Xcode Dev
//
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
int data;
struct LNode* next;
}lnode;
//基本操作
lnode* CreateLNode(int n);
int GetLinkLength(lnode *head);
int GetValue(lnode *head,int index);
int FindIndex(lnode *head,int value);
int Delete(lnode *head,int index);
int InsertValue(lnode *head,int index,int value);
void PrintLink(lnode *head);
//涉及算法
int Turn(lnode *head);
int main(void){
int temp=0;int value=0;
printf("输入_初始化元素(10个):");
lnode* test=CreateLNode(10);
printf("%d",test->data);
PrintLink(test);
printf("元素数量:%d\n",GetLinkLength(test));
Turn(test);
PrintLink(test);
printf("输入_位序:");
scanf("%d",&temp);
value = GetValue(test,temp);
printf("\n取得值:%d\n",value);
printf("输入_元素:");
scanf("%d",&temp);
value = FindIndex(test,temp);
printf("\n取得位序:%d\n",value);
printf("输入_待删除位序:");
scanf("%d",&temp);
if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
PrintLink(test);
printf("输入_待插入位序、数值:");
scanf("%d %d",&temp,&value);
if(InsertValue(test,temp,value))printf("\nsucceed");else printf("\nfaild!");
PrintLink(test);
}
//创建单链表
lnode *CreateLNode(int n){
lnode* p_head,*p_next,*p_loop;
int i;
p_next=p_head=(lnode*)malloc(sizeof(lnode));
for (i=1; i<=n; i++) {
p_loop=(lnode*)malloc(sizeof(lnode));
scanf("%d",&p_loop->data);
p_next->next=p_loop;
p_next=p_loop;
}
p_next->next=NULL;
return p_head;
}
//取得链表长度
int GetLinkLength(lnode *head){
lnode *p;int n;
n=0;
p=head->next;
while(p!=NULL){
n++;p=p->next;
}
return n;
}
//取得元素值
int GetValue(lnode *head,int index){
lnode *p;int j;
if(index<1)return 0;
j=1;p=head->next;
while(p!=NULL&&j<index){
p=p->next;j++;
}
if(p==NULL)return 0;
return p->data;
}
//查找元素索引
int FindIndex(lnode *head,int value){
int i = 1;
lnode *p_temp = head->next;
while(p_temp!=NULL&&p_temp->data!=value){
p_temp=p_temp->next;i++;
}
return i;
}
//删除元素
int Delete(lnode *head,int index){
lnode *p_1,*p_2;int j;
if(index<1&&index>GetLinkLength(head))
return 0;
p_1=head;j=0;
while(p_1->next!=NULL&&j<index-1){
p_1=p_1->next;j++;
}
p_2=p_1->next;
p_1->next=p_2->next;
free(p_2);
return 1;
}
//插入元素
int InsertValue(lnode *head,int index,int value){
lnode *p_1,*p_new;int j;
if(index<1)return 0;
p_1=head;j=0;
while(p_1!=NULL&&j<index-1){
p_1=p_1->next;j++;
}
if(p_1==NULL)return 0;
p_new=(lnode*)malloc(sizeof(lnode));
p_new->data=value;
p_new->next=p_1->next;
p_1->next=p_new;
return 1;
}
//打印链表
void PrintLink(lnode *head){
lnode *p;int index;
p=head->next;index=1;printf("\n");
while(p!=NULL){
printf("%3d:%-3d\t",index,p->data);
p=p->next;index++;
}
printf("\n");
}
//逆置元素
int Turn(lnode *head){
lnode *p,*q;
p=head->next;
head->next=NULL;
while(p!=NULL){//断头,然后头连屁股。重复。
q=p->next;
p->next=head->next;
head->next=p;
p=q;
}
return 1;
}
3、双链表
//
// DS03_DNode.c
// DS03_DNode
//
// Created by Remoo on 2022/9/26.
//
// Xcode Dev
//
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode{
int data;
struct DNode *next;//下一个节点 后驱节点
struct DNode *pr;//上一个节点 前驱节点
}dlink;
//基本操作
dlink* CreateDNode(int n);
int Insert(dlink *head,int index,int value);
int Delete(dlink *head,int index);
void PrintLink(dlink *head);//与LNode一样,只是增加了逆向输出的功能
int GetLinkLength(dlink *head);//与LNode一样
int GetValue(dlink *head,int index);//与LNode一样
int FindIndex(dlink *head,int value);//与LNode一样
//算法1
void Move(dlink *head);
int main() {
int temp=0;
dlink* test=CreateDNode(5);
PrintLink(test);
Move(test);
PrintLink(test);
printf("元素数量:%d\n",GetLinkLength(test));
Insert(test,2,100);
PrintLink(test);
printf("输入_待删除位序:");
scanf("%d",&temp);
if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
PrintLink(test);
}
//把所有大于等于0的数放在负数的前面
/*
分析:现将p赋值为位序1的地址,q赋值为链表尾部地址。
p从左向右寻找最近的非负数,q从右向左寻找负数,然后两者交换。循环上述操作。
*/
void Move(dlink *head){
dlink *p,*q;int temp;
p=head->next;
for (q=head; q->next!=NULL; q=q->next);//直接将q移动到节点的尾部
while(p!=q){
while(p!=q&&p->data>=0)p=p->next;
while(p!=q&&q->data<0)q=q->pr;
if(p!=q){
temp=p->data;
p->data=q->data;
q->data=temp;
}
}
}
//创建双链表
/*
分析:双链表的结构与单链表类似,只是多了一个前驱节点。
*/
dlink* CreateDNode(int n){
dlink *head,*p,*q;int i;
p=head=(dlink*)malloc(sizeof(dlink));//先给头节点指针、位序1的指针开辟内存空间
for(i=1;i<=n;i++){
q=(dlink*)malloc(sizeof(dlink));
scanf("%d",&q->data);
q->pr=p;
p->next=q;
p=q;
}
p->next=head->pr=NULL;//两端节点置空
return head;
}
//取得链表长度
/*
分析:与单链表一致。
*/
int GetLinkLength(dlink *head){
dlink *p;int n;
n=0;
p=head->next;
while(p!=NULL){
n++;p=p->next;
}
return n;
}
/*
分析:与单链表一致。
*/
int GetValue(dlink *head,int index){
dlink *p;int j;
if(index<1)return 0;
j=1;p=head->next;
while(p!=NULL&&j<index){
p=p->next;j++;
}
if(p==NULL)return 0;
return p->data;
}
/*
分析:与单链表一致。
*/
int FindIndex(dlink *head,int value){
int i = 1;
dlink *p_temp = head->next;
while(p_temp!=NULL&&p_temp->data!=value){
p_temp=p_temp->next;i++;
}
return i;
}
//删除链表
/*
分析:先确定删除位置i的合理性,包括输入值要大于等于1且小于链表长度。
其次将指针定位到需要删除的节点位序上。然后取出前驱节点和后驱节点。
将上一个节点的next地址赋值给下一个节点的pr,奖下一个节点的pr赋值给上一个节点的next。
最后free需要删除的节点即可。
*/
int Delete(dlink *head,int index){//index输入的是位序
dlink *n;int i;
if(index<1&&index>GetLinkLength(head))return 0;
n=head;i=0;
while(n->next!=NULL&&i!=index){
n=n->next;i++;
}//现在n已经指到了index的位置了
n->pr->next=n->next;
n->next->pr=n->next;
free(n);
return 1;
}
//插入元素
/*
首先判断输入i合理性,包括输入值要大于等于1且小于链表长度。
其次将指针n指向位序i。
创建malloc一个new节点,data赋值对应内容value。
new节点的后驱节点是原位序为i的地址,new的前驱节点是原位序为i的前驱节点。
然后将原位序为i的前驱节点的后驱节点改为new的地址,将原位序为i的前驱节点改为new的地址。
*/
int Insert(dlink *head,int index,int value){
dlink *n,*new;int i;
if(index<1&&index>GetLinkLength(head))return 0;
n=head;i=0;
while(n->next!=NULL&&i!=index){
n=n->next;i++;
}//现在n已经指到了index的位置了
new=(dlink*)malloc(sizeof(dlink));
new->data=value;
new->next=n;
new->pr=n->pr;
n->pr->next=new;//这一行需要小心
n->pr=new;
return 1;
}
//打印链表
void PrintLink(dlink *head){
dlink *p;int index;
p=head;index=0;printf("\n顺序输出:");
while(p->next!=NULL){
p=p->next;index++;
printf("%3d:%-3d\t",index,p->data);
}
printf("\n逆序输出:");
while(p!=head){
printf("%3d:%-3d\t",index,p->data);
p=p->pr;index--;
}
printf("\n");
}
4、循环单向链表
//
// main.c
// DS04_circleList
//
// Created by Remoo on 2022/9/27.
//
// Xcode Dev
//
#include <stdio.h>
#include <stdlib.h>
typedef struct CNode{
int data;
struct CNode *next;
}cnode;
//基本算法
cnode *CreateList(int n);
int GetLinkLength(cnode *head);
int GetValue(cnode *head,int index);
int FindIndex(cnode *head,int value);
int Delete(cnode *head,int index);
int InsertValue(cnode *head,int index,int value);
void PrintLink(cnode *head);
//创建循环链表
cnode *CreateCNode(int n){
cnode *head,*p,*s;
int i;
p=head=(cnode*)malloc(sizeof(cnode));
for(i=1;i<=n;i++){
s=(cnode*)malloc(sizeof(cnode));
scanf("%d",&s->data);
p->next=s;
p=s;
}
p->next=head;//尾巴指向头部,即为循环单链表。其余和单链表一致。
return head;
}
//取得链表长度
int GetLinkLength(cnode *head){
cnode *p;int n;n=0;
p=head->next;
while(p!=head){//只有这一个地方与单链表相异
n++;p=p->next;
}
return n;
}
//取元素操作
int GetValue(cnode *head,int index){
cnode *p;int j;
if(index<1)return 0;
j=1;p=head->next;
while(p!=head&&j<index){//这里与单链表相异
p=p->next;j++;
}
if(p==head)return 0;//这里与单链表相异
return p->data;
}
//查找元素索引
int FindIndex(cnode *head,int value){
int i = 1;
cnode *p_temp = head->next;
while(p_temp!=head&&p_temp->data!=value){//这里与单链表相异
p_temp=p_temp->next;i++;
}
return i;
}
//删除元素
int Delete(cnode *head,int index){
cnode *p_1,*p_2;int j;
if(index<1&&index>GetLinkLength(head))
return 0;
p_1=head;j=0;
while(p_1->next!=head&&j<index-1){//这里与单链表相异
p_1=p_1->next;j++;
}
p_2=p_1->next;
p_1->next=p_2->next;
free(p_2);
return 1;
}
//插入元素
int InsertValue(cnode *head,int index,int value){
cnode *p_1,*p_new;int j;
if(index<1)return 0;
p_1=head;j=0;
while(p_1->next!=head&&j<index-1){//这里与单链表相异
p_1=p_1->next;j++;
}
if((p_1->next!=head)||(p_1->next==head&&j==index-1)){//这里与单链表相异
p_new=(cnode*)malloc(sizeof(cnode));
p_new->data=value;
p_new->next=p_1->next;
p_1->next=p_new;
return 1;
}
else return 0;
}
//打印链表
void PrintLink(cnode *head){
cnode *p;int index;
p=head->next;index=1;printf("\n");
while(p!=head){//这里与单链表相异
printf("%3d:%-3d\t",index,p->data);
p=p->next;index++;
}
printf("\n");
}
int main() {
int temp=0;int value=0;
printf("输入_初始化元素(10个):");
cnode* test=CreateCNode(10);
printf("%d",test->data);
PrintLink(test);
printf("元素数量:%d\n",GetLinkLength(test));
printf("输入_位序:");
scanf("%d",&temp);
value = GetValue(test,temp);
printf("\n取得值:%d\n",value);
printf("输入_元素:");
scanf("%d",&temp);
value = FindIndex(test,temp);
printf("\n取得位序:%d\n",value);
printf("输入_待删除位序:");
scanf("%d",&temp);
if(Delete(test,temp))printf("\nsucceed");else printf("\nfaild!");
PrintLink(test);
printf("输入_待插入位序、数值:");
scanf("%d %d",&temp,&value);
if(InsertValue(test,temp,value))printf("\nsucceed");else printf("\nfaild!");
PrintLink(test);
}
标签:index,head,temp,int,next,printf,共享,源代码,DS From: https://www.cnblogs.com/remyuu/p/16734773.html