Tag:数据结构

Tag (数据结构)'s result:

Circular links

循环链表是使最后一个结点的next指针指向表头结点,构成循环,这里我只实现了循环链表的创建和打印操作。 #include <stdio.h> #include <malloc.h> typedef struct lnode { int data; struct lnode *next; } LNODE,*linklist; //打印链表元素 void print_list(linklist L) { linklist p; printf(“建立的循环链表为:\n”); p = L->next; //指向结点(非头结点) while (p!=L) { printf(“%d “,p->data); p=p->next; } printf(“\n”); } //创建循环链表 void creat_list(linklist L) { linklist p,q; L->next = L; //指向自己 printf(“请输入链表元素:\n”); q = (linklist)malloc(sizeof(LNODE)); scanf(“%d”,&(q->data)); q->next = L->next; //q的后指针指向头结点 L->next = q; //头结点的后指针指向新开的q p = (linklist)malloc(sizeof(LNODE)); while ((scanf(“%d”,&(p->data)))!=EOF) { p->next = q->next; //新开的p的后指针指向前一个q的后指针 q->next = p; //q的后指针指向新开的p q = p; //q记录 p=(linklist)malloc(sizeof(LNODE)); //p再新开 } } int main() { linklist L; //是地址 L = (linklist)malloc(sizeof(LNODE)); creat_list(L); print_list(L); return 0; }

Two-way linked-list

双向链表在链表的基础上新增了指向前一个结点的指针prior, 由于链表没设表长属性,我在程序用了count变量记录表长以方便插入操作。这里我实现的是双向链表的创建,打印,插入和删除操作。 #include <stdio.h> 2 #include <malloc.h> 3 4 typedef struct shuang 5 { 6 struct shuang *prior; //指向前一个结点 7 int data; 8 struct shuang *next; //指向后一个结点 9 } snode, *slinklist; 10 11 //打印双向链表元素 12 void print_shuang(slinklist L) 13 { 14 slinklist p; 15 p = L->next; 16 while (p!=NULL) 17 { 18 printf(“%d “,p->data); 19 p = p->next; 20 } 21 printf(“\n”); 22 } 23 24 //创建双向链表 25 void creat_shuang(slinklist L) //得结点地址 26 { 27 slinklist p,q; 28 L->next = NULL; //头结点的后指针先指向null 29 printf(“请输入链表元素\n”); 30 q = (snode *)malloc(sizeof(snode)); 31 scanf(“%d”,&(q->data)); 32 q->next = L->next; //NULL给了q->next 33 L->next = q; //L(头结点)指向新的q 34 q->prior = L; //新的q的前指针指向前一个L 35 p = (snode *)malloc(sizeof(snode)); 36 while (scanf(“%d”,&(p->data))!=EOF) 37 { 38 p->next = q->next; //p的后指针指向q的后指针 39 q->next = p; //q的后指针改为指向新的p 40 p->prior = q; //新的p的前指针指向上一个q 41 q = p; //上一个q变成这次新的p(q记录p) 42 p = (snode *)malloc(sizeof(snode)); //p再新开 43 } 44 } 45 46 //插入 47 int ins(slinklist L,int i,int e) 48 { 49 slinklist p,q,s; 50 int j = 1; 51 int count =……

LinkedList

链表的结点中有指针域,这里先写最初级的链表(后续会有链表的进化型和究极进化型) 几个关键点: 1.头指针 2.插入和删除操作的指针修改 3.插入和删除操作的各种情况分析(具体的看注释) 4.记录指针 下面以一个学生成绩管理程序为例: #include <stdio.h> #include <malloc.h> #define NULL 0 struct student { int num; //学号 double score; //分数 struct student *next; //指向下一个学生 }; int main() { struct student *del(struct student *head,int num); //删除声明 struct student *ins(struct student *head,struct student *stu); //插入声明 int n = 0; int dnum; struct student *head,*p,*p1,*p2,*p3,stu; head = NULL; //先让头结点指针为空 p1 = (struct student*)malloc(sizeof(struct student)); //开辟空间 scanf(“%d%lf”,&p1->num,&p1->score); do { n = n+1; if (n==1)head = p1; //若是第一个结点,就给head else p2->next = p1; //非第一个结点,就给p2的下一个结点 p2 = p1; //把p1先给p2 p1 = (struct student*)malloc(sizeof(struct student)); //p1再新开一个内存区 scanf(“%d%lf”,&p1->num,&p1->score); } while (p1->num!=0); //号数输入为0就结束了 p2->next = NULL; //最后一个结点的next指向null没了 p = head; //创建链表完毕————————————– while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; //指针后移输出结点信息 } printf(“请输入需要删除的学号:”); scanf(“%d”,&dnum); p = del(head,dnum); //返回删除后的头结点,删除完毕—————————— p3 = p; //记录删除后的链表! while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; } printf(“请输入需要增添的学号及其数据”); scanf(“%d%lf”,&stu.num,&stu.score); p = ins(p3,&stu); //返回插入后的头结点,插入完毕——————————- while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; } return 0; } struct student *del(struct student *head,int num) //传头结点与要删除的号数进来 { struct student *p1,*p2; if (head==NULL) { printf(“NO\n”); } p1 = head; while (num!=p1->num&&p1->next!=NULL) //要删除的号数不是第一个并且没到或等于最后一个……

Sequential table

对顺序表进行初始化,创建,插入,删除和查找操作 #include <stdio.h> 3 4 #define list_init_size 100 5 #define listincrement 10 6 7 typedef struct 8 { 9 int *elem; 10 int length; 11 int listsize; 12 } sqlist; 13 14 //初始化顺序表 15 int init(sqlist *L) 16 { 17 L->elem = (int *)malloc(list_init_size *sizeof(int)); //分配空间 18 if (!L->elem) 19 { 20 return 0; 21 } 22 L->length = 0; //初始化顺序表元素个数为0 23 L->listsize = list_init_size; //最大长度为100 24 return 1; 25 } 26 27 //创建顺序表 28 void createlist(sqlist *L,int len) 29 { 30 if (len>=list_init_size) //如果元素个数大于等于顺序表长度,设等于为了方便后续插入操作 31 { 32 L->elem=(int *)realloc(L->elem,len *sizeof(int)); //新增空间 33 L->listsize = len; //修改最大长度为len 34 } 35 36 printf(“请输入顺序表元素\n”); 37 for (int i=1; i<=len; i++) //注意:是从1开始创建! 38 { 39 scanf(“%d”,&L->elem[i]); 40 } 41 42 L->length = len; //元素个数赋值为len 43 printf(“创建的顺序表为:\n”); 44 for (i=1; i<=len; i++) 45 { 46 printf(“%d “,L->elem[i]); 47 } 48 printf(“\n此顺序表共%d个元素\n”,L->length); 49 } 50 51 //插入 52 int ins(sqlist *L,int i,int x) 53 { 54 int j; 55 if (L->length==L->listsize) 56 { 57 printf(“顺序表已满,无法插入\n”); 58 return 0; 59 } 60 61 else 62 {……

Sequential stack

栈(stack)是先进后出的一种数据结构,要注意栈顶指针的移动,而且只能在栈顶进行操作。 #include <stdio.h> #include <stdlib.h> typedef struct { char stack[10]; //利用数组模拟栈 int top; //栈顶指针 } qstype; //初始化 void init(qstype *s) { s->top=-1; } //入栈 int push(qstype *s,int x) { if (s->top>=9) //0~9 10个元素 { return 0; } else { s->top++; //下标要从0开始 s->stack[s->top] = x; return 1; } } void main() { int ch,sign; qstype *s; s = (qstype *)malloc(sizeof(qstype)); init(s); printf(“顺序栈建立成功\n”); printf(“请输入数据并以-1结束\n”); scanf(“%d”,&ch); while (ch!=-1) { if ((sign=push(s,ch))==0) { printf(“数据溢出\n”); break; } else { scanf(“%d”,&ch); } } printf(“输出栈中元素\n”); //倒序输出(后进先出) while (s->top!=-1) //top最大是9 { s->top–; printf(“%d “,s->stack[s->top+1]); } printf(“\n”); }

Sequential queue

顺序队列是一种先进先出的数据结构,利用头指针和尾指针操作元素 #include <stdio.h> #include <stdlib.h> typedef struct { int queue[10]; int front; int rear; } qqtype; //初始化队列 void init(qqtype *q) { q->front = -1; q->rear = -1; } int enterline(qqtype *q,int x) //入队 { if (q->rear==9) //0~9 10个元素 return 0; else { q->rear++; //下标从要0开始 q->queue[q->rear]=x; return 1; } } int main() { int ch,sign; qqtype *q; q = (qqtype *)malloc(sizeof(qqtype)); init(q); printf(“creat success\n”); printf(“please input the data\n”); scanf(“%d”,&ch); while (ch!=-1) { if ((sign = enterline(q,ch))!=1) break; scanf(“%d”,&ch); } printf(“output the data\n”); while (q->front!=q->rear) //队满时,front为-1,rear为9 { q->front++; printf(“%d “,q->queue[q->front]); } printf(“\n”); return 0; }

Circular queue

将顺序队列想象成一个环,约定以队列头指针在队列尾指针的下一位置上作为队列满的状态,需要空出一个位置给头指针。 #include <stdio.h> #include <stdlib.h> typedef struct { int queue[10]; int front; int rear; } qqtype; //初始化 void init(qqtype *q) { q->front = 0; q->rear = 0; } int enterline(qqtype *q,int x) { if ((q->rear + 1) % 10==q->front) //如果尾指针移到了头指针前一个位置,队列就满了(1~9共9个元素,空了个位置),rear最大为9 return 0; else { q->rear = (q->rear + 1) % 10; q->queue[q->rear] = x; //下标从1开始了! return 1; } } int main() { int ch,sign; qqtype *q; q = (qqtype *)malloc(sizeof(qqtype)); init(q); printf(“creat C success\n”); printf(“please input the data\n”); scanf(“%d”,&ch); while (ch!=-1) { if ((sign = enterline(q,ch))!=1) break; scanf(“%d”,&ch); } printf(“output the data\n”); while (q->front!=q->rear) //front为0 { q->front = (q->front+1) % 10; printf(“%d “,q->queue[q->front]); } printf(“\n”); return 1; }

稀疏矩阵快速转置

问: 1.什么是稀疏矩阵? 答: 假设在m*n的矩阵中,有t个元素不为0,令&=t/(m*n),&就是矩阵的稀疏因子,通常认为&<=0.05时称为稀疏矩阵。——–摘自《数据结构(C语言版)》 2.什么是转置? 答:在矩阵M中,每个元素的行和列互换,构成新的矩阵T,T即M的转置矩阵,行列互换就是转置(Mij = Tji)。 3.什么是三元组? 答:稀疏矩阵中每个非0元的行标,列标和数值构成一个三元组。 4.什么是三元组表? 答:稀疏矩阵中的每个非0元构成的三元组放在一起,加上稀疏矩阵的总行数,总列数和非0元总数构成三元组表。 5.为什么我看不懂fastt函数的最后一个for循环啊?(哈哈别问我为什么知道,因为我也想了很久才懂) 答:自己模拟一遍,看看注释。 公式:计算M中第col列的第一个非0元素在T三元组表中的位置 cpot[1] = 1; cpot[col] = cpot[col-1] + num[col-1]; #include <stdio.h> typedef struct { int i,j; int e; } triple; //存行标,列标,数值 typedef struct //三元组表 { triple data[1000+1]; //非0元的信息 int numh,numl,tu; } ts; //存三元组,总行数,总列数,非零元素总数 int fastt(ts M,ts &T) { int col,p,q,t; int num[1000],cpot[1000]; //num存M中第col列中非0元素个数,cpot存M中第col列的第一个非0元素在T中的位置 T.numh = M.numl; T.numl = M.numh; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.numl; col++) { num[col] = 0; //初始化全部0 } for (t=1; t<=M.tu; t++) { num[M.data[t].j]++; //计算每一列非零元素个数 } cpot[1] = 1; //固定的 for (col=2; col<=M.numl; col++) { cpot[col] = cpot[col-1] + num[col-1]; //公式,计算M每列第一个非零元素转置后在T三元组表的位置 } for (p=1; p<=M.tu; p++) { col = M.data[p].j; q = cpot[col]; //如果一列中不止一个元素,后面的++就有用了 T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; //Tij = Mji T.data[q].e = M.data[p].e; cpot[col]++; //加1为这一列的下一个非0元素做准备 } } return 1; } void creatzz(ts &M) { printf(“请输入稀疏矩阵非零元素个数\n”); scanf(“%d”,&M.tu); printf(“请输入稀疏矩阵行数\n”); scanf(“%d”,&M.numh); printf(“请输入稀疏矩阵列数\n”); scanf(“%d”,&M.numl); printf(“输入稀疏矩阵非零元素三元组信息\n”); for (int k=1; k<=M.tu; k++) { printf(“第%d个元素的行标:”,k); scanf(“%d”,&M.data[k].i); printf(“第%d个元素的列标:”,k); scanf(“%d”,&M.data[k].j); printf(“此元素值:”); scanf(“%d”,&M.data[k].e); } } void printM(ts &M) { int p,q,t = 1,e = 0,flag =……

链队列

链队列带有头结点(不存数值,只为方便操作),队尾指针存有元素,这里我实现了链队列的初始化,插入,删除,销毁操作 #include <stdio.h> #include <stdlib.h> typedef struct Qnode { int data; struct Qnode *next; } Qnode,*Qptr; typedef struct { Qptr f; Qptr r; } linkqueue; int initqueue(linkqueue &Q) //初始化队列 { Q.f = Q.r = (Qptr)malloc(sizeof(Qnode)); //动态分配空间,队头和队尾指针要指向同一个地址 if (Q.f) return 0; Q.f->next = NULL; return 1; } int ins(linkqueue &Q,int e) { Qptr p; p = (Qptr)malloc(sizeof(Qnode)); //生成结点 if (!p) return 0; p->data = e; //尾插 p->next = NULL; Q.r->next = p; Q.r = p; //更新尾结点 return 1; } int del(linkqueue &Q) { Qptr p; int e; if (Q.f==Q.r) return 0; //判空 p = Q.f->next; e = p->data; Q.f->next = p->next; if (Q.r==p) Q.r = Q.f; //如果队列就一个尾结点,删掉就空了 free(p); return e; } void destroy(linkqueue &Q) { while (Q.f) { Q.r = Q.f->next; free(Q.f); Q.f = Q.r; } printf(“链队列销毁完毕!\n”); } void printqueue(linkqueue Q) { Qptr p; p = Q.f; printf(“此时链队列中的元素为:\n”); while (p->next) { printf(“%d “,p->next->data); p = p->next; } } int main() { int x,m; linkqueue Q; initqueue(Q); printf(“请输入插入到链队列中的元素值\n”); while (scanf(“%d”,&x)!=EOF) { ins(Q,x); } printqueue(Q); printf(“\n删除队头元素\n”); m = del(Q); printf(“删除的元素是%d\n”,m); printqueue(Q); return 0;……

链栈

链栈设了一个栈顶指针,这里我实现了插入,删除,判空,打印操作 #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } StackNode; StackNode *top = NULL; void push(int e) { StackNode *p; p = (StackNode *) malloc (sizeof(StackNode)); p->data = e; //头插 p->next = top; top = p; //更新栈顶指针 } bool isEmpty() { return top==NULL ? true:false; } int pop() { StackNode *p; int e; if (isEmpty()) { printf(“The stack is empty, failed to pop!\n”); return NULL; } p = top; e = p->data; top = top->next; free(p); return e; } void print() { StackNode *p; p = top; if (isEmpty()) { printf(“The stack is empty!\n”); return; } printf(“\n”); while (p) { printf(“%d “, p->data); p = p->next; } printf(“\n”); } int main() { int x,n1,n2,n; printf(“请输入入栈元素个数\n”); scanf(“%d”,&n); while (n–) { scanf(“%d”,&x); push(x); } n1 = pop(); n2 = pop(); printf(“%d\n%d”,n1,n2); print(); return 0; }