【数据结构(C语言)】数据结构

2024-01-05 07:19| 来源: 网络整理| 查看: 265

数据结构-表【知识索引】【数据结构(C语言)】一、线性表(1)基本概念1.定义(性质相同的数据元素构成的有限序列)2.表长,空表,位序,直接前驱,直接后继3.基本操作(12) (2)存储结构1.顺序表2.链表二、栈和队列(1)栈1.基本概念2.存储结构3.栈的应用 (2)队列1.基本概念2.存储结构三、串(1)基本概念及术语1.概念2.ADT (2)基本操作1.最小操作子集2.其他操作 (3)串的表示方法1.顺序存储结构2.链式存储结构 (3)串的应用1.文本编辑四、数组和广义表(1)数组1.数组的定义2.数组的顺序表示3.矩阵的压缩存储 (2)广义表1.定义文章索引

【知识索引】【数据结构(C语言)】

在这里插入图片描述

一、线性表 (1)基本概念 1.定义(性质相同的数据元素构成的有限序列) 2.表长,空表,位序,直接前驱,直接后继 3.基本操作(12)

InitList(&L); //构造一个空的线性表L ListEmpty(L); //判断线性表L是否是空表，若是，则返回TRUE，否则返回FALSE ListLength(L); //返回线性表L的长度 GetElem(L,i,&e) ; //用e返回线性表L的第i个数据元素的值 LocateElem(L,e,compare());//在线性表L中查找第一个和元素e满足compare关系//的元素，若找到则返回其位序；否则返回0 PriorElem(L,e, &pre_e); //用pre_e返回线性表L中元素e的直接前驱 NextElem(L, e, &next_e); //用next_e返回线性表L中元素e的直接后继 ListInsert(&L,i,e) ; //将数据元素e插入到线性表L的第i个数据元素之前 ListDelete(&L,i,&e); //删除线性表L的第i个数据元素，并将其值用e返回 ListTraverse(L,visit()); //依次对线性表L中的每个元素调用visit进行访问 ClearList(&L); //重置线性表L为空表 DestroyList(&L); //销毁线性表L，可能的话释放其空间

(2)存储结构 1.顺序表

用一组地址连续的存储单元依次存储线性表的数据元素。用顺序存储结构表示的线性表又称为顺序表。

存储类型定义 #define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配量 #define LISTINCREMENT 10 //顺序表存储空间的分配增量 typedef struct { ElemType *elem; //存储空间的基地址 int length; //顺序表的当前长度 int listsize; //数组存储空间的长度 }SqList;

特点

逻辑上相邻的数据元素在物理位置上也相邻随机存取

基本操作

初始化顺序表

Status InitSqList(SqList& L) //顺序表初始化 { L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//申请初始分配空间 if (L.elem == NULL) exit(OVERFLOW);//分配失败,返回OVERFLOW L.length = 0;//初始化表长为零 L.listsize = LIST_INIT_SIZE;//初始化数组存储空间为初始分配空间 return OK;//分配成功返回OK }

销毁顺序表

void DestroySqList(SqList& L)//销毁顺序表 { if (L.elem != NULL)//如果顺序表存在 free(L.elem);//释放存储空间 L.elem = NULL;//存储空间基址置空 }

顺序表判空

Status SqListEmpty(SqList L)//顺序表的判空操作 { if (L.length == 0) return TRUE;//表长为零为空表 else return FALSE;//表长非零不为空 }

顺序表求表长

int SqListLength(SqList L)//顺序表求表长 { return L.length; }

获取元素

Status GetSqElem(SqList L, int i, ElemType& e)//取第i个元素,用第三个参数e返回 { if (iL.length)//判断索引是否有效 return ERROR;//无效报错 else { e = L.elem[i - 1];//有效则返回元素 return OK; } }

定位操作

int SqLocateElem(SqList L, ElemType e)//定位元素e,返回元素位序,若元素不存在则返回零 { int i; for (i = 1; i if (iL.length)//判断位序是否有效 return ERROR; if (L.length == L.listsize)//判断是否溢出,如果溢出,重新分配空间 { L.elem = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.listsize += LISTINCREMENT; } ElemType* q; q = &L.elem[i - 1]; for (ElemType* p = &L.elem[L.length - 1]; p >= q; p--)//从后向前移动元素 { *(p + 1) = *p; } *q = e; L.length++;//更新表长 return OK; }

删除操作

Status SqListDelete(SqList& L, int i)//删除顺序表第i个元素 { if (iL.length) //判断参数是否溢出 return ERROR; int j; for (j = i; j int i; for (i = 0; i //算法2.7 pa=la.elem; pb=lb.elem; lc.listsize=lc.length=la.length+lb.length; pc=lc.elem = new ElemType[lc.listsize]; pa_last=la.elem+la.length-1; pb_last=lb.elem+lb.length-1; while(pa for(i=0,j=A.length-1;i L = (LinkList)malloc(sizeof(LNode));//申请头节点 if (L == NULL) exit(OVERFLOW);//申请失败返回异常 L->next = NULL;//头节点置空 return OK; }

单链表的判空操作

Status LinkListEmpty(LinkList L) //单链表的判空操作 { if (L->next == NULL)//判断头指针是否为空 return TRUE; else return FALSE; }

销毁单链表

void DestroyLinkList(LinkList& L) //销毁单链表 { LinkList p;//新建节点指针 while (L != NULL)//头指针非空 { p = L->next;//p指针保留将要释放的节点指针域 free(L);//释放节点 L = p;//更新头节点 } }

单链表求表长

int LinkListLength(LinkList L) //单链表求表长操作 { LinkList p; int n = 0; for (p = L->next; p != NULL; p = p->next, n++);//从首元节点遍历单链表并计数 return n; }

清空单链表

void ClearLinkList(LinkList L) //清空单链表 { LinkList p; for (p = L->next; p != NULL; p = L->next)//从首元节点遍历释放节点空间 { L->next = p->next;//更新头节点指针 free(p);//释放首元节点 } }

单链表取值

Status GetLinkElem(LinkList L, int i, ElemType& e) //单链表取第i个值,由e返回 { int count;//计数变量 LinkList p = L;//遍历指针初始为头指针 for (count = 0; count e = p->data; return OK; } }

单链表定位

LinkList LinkLocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) //单链表定位操作,返回第一个满足关系的节点指针,若无满足关系的元素,返回空指针 { LinkList p = L->next;//从首元节点遍历链表 while (p!=NULL && compare(p->data, e)==FALSE) //直到满足关系或遍历结束停止遍历 p = p->next; return p;//返回指针 }

单链表插入操作

Status LinkListInsert(LinkList& L, int i, ElemType e)//单链表插入操作 { int count;//计数变量 LinkList p;//循环指针 for (count = 0, p = L; count next, count++);//定位第i-1个节点 if (i int count;//计数变量 LinkList p;//循环指针 for (count = 0, p = L; count next, count++);//定位第i-1个节点 if (i LinkList p; for (p = L->next; p; p = p->next) if (!visit(p->data)) return ERROR; return OK; }

应用

逆向建立n个元素的单链表

void CreateList_backward(LinkList &L，int n) { //逆向建立n个元素的单链表 L=( LinkList) malloc(sizeof(LNode)); L->next=NULL; for(i=0; i ElemType data; Struct DulNode *prior;//指向其直接前驱的指针域 Struct DulNode *next; //指向其直接后继的指针域 }DulNode,*DuLinkList;

操作

某些操作算法与线性单链表的操作相同；插入、删除等操作需同时修改两个方向的指针

插入

Status ListInsert_Dul(DuLinklist &L,int i,ElemType e) { if(!(p=GetElem_DuL(L,i))) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data=e; ① s->prior=p->prior; ② p->prior->next=s; ③ s->next=p; ④ p->prior=s; return OK; }

删除

Status ListDelete_Dul(DuLinklist &L,int i,ElemType &e) { if(!(p=GetElem_DuL(L,i))) return ERROR; e=p->data; ① p->prior->next=p->next ; ② p->next->prior=p->prior; ③ free(p); return OK; } 二、栈和队列 (1)栈 1.基本概念

栈：限制仅在表的一端进行插入和删除的线性表

ADT定义

ADT Stack { 数据对象：D={ai| ai  ElemSet, i=1,2,…,n, n0} 数据关系：R={| ai-1，ai D，i=2,…,n} 约定an端为栈顶， a1端为栈底基本操作：InitStack（&S）; StackEmpty(S); StackLength(&S); GetTop(S, &e); Push(&S, e); Pop(&S, &e); ClearStack(&S); StackTraverse(S, visit()); DestroyStack(&S); } ADT Stack

栈顶：允许插入、删除的一端。

栈底：与栈顶相对的另一端。

空栈：表中没有元素的栈

2.存储结构

顺序栈

特点：用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素栈中元素可动态增删，即栈长是可变的，因此和顺序表一样，用动态分配的一维数组来表示顺序栈

存储结构的定义

#define STACK_INIT_SIZE 100 //顺序栈存储空间的初始分配量 #define STACKINCREMENT 10 //顺序栈存储空间的分配增量 typedef struct { SElemType* base; //栈底指针，始终指示存储空间的基址 SElemType* top; //栈顶指针，指向栈顶元素的下一个位置 int stacksize; //数组存储空间的长度 }SqStack;//顺序栈定义栈底指针，始终指示存储空间的基址栈顶指针，指向栈顶元素的下一个位置数组存储空间的长度

基本操作

构造空栈

Status InitSqStack(SqStack& S) { S.base = (SElemType*)malloc((STACK_INIT_SIZE) * sizeof(SElemType));// 栈的连续空间分配 if (!S.base) { exit(OVERFLOW); } S.top = S.base; //空栈，初始化栈顶指针 S.stacksize = STACK_INIT_SIZE; return OK; }//构造一个空栈，该栈由指针S指示

销毁栈

Status DestroySqStack(SqStack& S) { if (S.base) //栈底指针非空 free(S.base); S.base = NULL; return OK; }//销毁栈

清空栈

Status ClearSqStack(SqStack& S) { S.top = S.base; return OK; }//清除栈

判空

Status SqStackEmpty(SqStack S) { return S.top == S.base; }//栈的判空操作

求栈长

int SqStackLength(SqStack S) { return S.top - S.base; }//求栈长

取栈顶元素

Status GetTopSq(SqStack S, SElemType& e) { if (S.top == S.base) return ERROR; e = *(S.top - 1); return OK; } //用指针e带回栈顶元素

入栈

Status SqPush(SqStack& S, SElemType e) {//入栈，插入元素e为新的栈顶元素 if (S.top - S.base == S.stacksize)//栈满 { S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; }//重新分配更大的连续空间 *S.top++ = e; return OK; }//Push

出栈

Status SqPop(SqStack& S, SElemType& e) { if (S.top == S.base) //栈空 return ERROR; --S.top; e = *S.top; return OK; }//出栈，删除的栈顶元素用指针e指示

遍历

Status SqStackTraverse(SqStack S, Status(*visit)(SElemType)) {//从栈底到栈顶依次对栈S中的每个数据元素调用visit //指向的函数进行访问 SElemType* p; for (p = S.base; p //插入e到栈S中使之成为新的栈顶元素 p=( LinkStack)malloc(sizeof(SNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=S; S=p; return OK; }//Push

链栈出栈

Status Pop(LinkStack &S, SElemType &e) {//若栈不空则出栈，删除的栈顶元素用e指示 if(!S) return ERROR; //栈空 p=S; S=S->next; e=p->data; free(p); return OK; }//Pop 3.栈的应用

数制转换

括号匹配的检验

迷宫求解

Typedef struct { //栈的元素类型定义 int ord; //通道块在路径上的“序号” PosTpye seat ; //通道块在迷宫中的“坐标位置” int di; //从此通道块走向下一通道块的“方向” ｝SElemType； Status MazePath（MazeType maze, PosType start, PosType end）{ InitStack(s); curpos=start; //设定当前位置为入口位置 curstep =1; do{ if(Pass(curpos)) { //当前位置可通 FootPrint(curpos); //留下足迹 e=(curstep, curpos, 1); push(s,e); //加入路径 if(curpos==end) return(TRUE); //到达终点 curpos= NextPos(curpos, 1); //下一位置是当前位置的东邻 curstep++; //探索下一步｝//if else { //当前位置不能通过 if (!StackEmpty(S)) { Pop(S,e); while(e.di==4 && !StackEmpty(s)){ MarkPrint(e.seat); Pop(s,e); //留下不能//通过的标记，并退回一步｝//while if (e.di InitStack(OPTR); Push(OPTR, '#'); InitStack(OPND); c=getchar(); while(c!= '#' || GetTop(OPTR)!= '#'){ if (!In(c,OP)) {Push(OPND,c); c=getchar();} else switch(Precede(GetTop(OPTR),c)){ case '': Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; }//switch }//while return GetTop(OPND); }// EvaluateExpression

栈与递归

(2)队列 1.基本概念

队列：只允许在表的一端进行插入，而在另一端进行删除的线性表。

ADT

ADT Queue { 数据对象：D={ai | ai  ElemSet, i=1,2,…,n, n>=0} 数据关系：R={< ai-1, ai > | ai-1, ai D， i=2,3，…,n} 约定a1端为队头，an端为队尾基本操作：InitQueue(&Q); QueueEmpty(Q); QueueLength(Q); GetHead(Q, &e); EnQueue(&Q, e); DeQueue(&Q, &e); ClearQueue(&Q); QueueTraverse(Q, Visit()); DestroyQueue(&Q); }ADT Queue

队头：允许删除的一端

队尾：允许插入的一端

空队列：没有元素的队列

双端队列：限定插入和删除操作在表两端进行的线性表

输出受限队列:一端允许插入和删除，另一端只允许插入。

输入受限队列:一端允许插入和删除，另一端只允许删除。

2.存储结构

链队列

使用二个指针分别记录队头和队尾的当前位置设立一个头结点，并令头指针指向头结点，头结点的指针域指向队头元素所在的结点链队列的判空条件：头指针和尾指针均指向头结点

链队列类型定义

typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; //头指针 QueuePtr rear; //尾指针 }LinkQueue; ```

基本操作

链队列入队

Status EnQueue(LinkQueue &Q, ElemType e) { p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; //尾指针指向新的尾结点 return OK; }// EnQueue

链队列入出队

Status DeQueue(LinkQueue &Q, ElemType &e) { if(Q.rear == Q.front) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; //若队头元素是队列中唯一的一个元素, 则删除该结点后//还需要修改尾指针，让它指向头结点 free(p); return OK; } // DeQueue

顺序队列

普通顺序队列

用一组地址连续的存储单元依次存储从队头到队尾的数据元素。

顺序队列类型定义

#define MAXQSIZE 100 typedef struct { QElemType *base; //存储空间基地址 int front;//队头指针，指向队头元素 int rear;//队尾指针，指向队尾元素的下一个位置 }SqQueue;

假上溢现象

循环队列

存储结构定义

少用一个元素空间，约定队列头指针在队尾指针下一个位置为队列满

#define MAXQSIZE 100 typedef int QElemType; typedef struct { QElemType* base; //存储空间基地址 int front;//队头指针，指向队头元素 int rear;//队尾指针，指向队尾元素的下一个位置 }SqQueue;

另设标志位区别队列空、满

typedef struct { ElemType *base; int front; int rear; int tag; }SqQueue;

基本操作

初始化队列

Status InitSqQueue(SqQueue& Q)//初始化队列 { Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType)); if (Q.base == NULL) exit(OVERFLOW); Q.front = Q.rear = 0;//队头队尾指针都指向0 return OK; }

求队长

int SqQueueLength(SqQueue Q)//求队长 { return(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; }

进队

Status EnSqQueue(SqQueue& Q, QElemType e)//进队操作 { if ((Q.rear + 1) % MAXQSIZE == Q.front) //队列满的判定条件（防止队满和队空无法区分，留下一个位置不用 return ERROR; //队满直接报错，不再申请更大的内存 else { Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针后移，%MAXQSIZE使下标首尾相接 return OK; } }

出队

Status DeQueue(SqQueue& Q, QElemType& e)//出队操作 { if (Q.front == Q.rear) //队空的判定条件 return ERROR; //队空报错 else { e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK; } }

判空

Status SqQueueEmpty(SqQueue Q)//循环队列的判空操作 { if (Q.rear == Q.front) return TRUE; else return FALSE; }

取队头元素

Status GetSqHead(SqQueue Q, QElemType& e)//取队头元素 { if (Q.rear == Q.front) return ERROR; else { e = Q.base[Q.front]; return TRUE; } }

清空队列

Status ClearSqQueue(SqQueue& Q)//清空队列 { Q.rear = Q.front; return OK; }

销毁队列

Status DestroySqQueue(SqQueue& Q)//销毁队列 { free(Q.base); Q.front = Q.rear = 0; return OK; }

队列的遍历

Status SqQueueTraverse(SqQueue Q, Status (*visit)(QElemType)) { int i; for (i = Q.front; i != Q.rear; i = (i + 1) % MAXQSIZE) {visit(Q.base[i]);} return OK; } 三、串 (1)基本概念及术语 1.概念

串：

由零个或多个字符组成的有限序列。记为：s= ‘a1 a2…an’ (n>=0)

串名: s

串值: a1a2a3……an

串长: n

空串：串长为0的串。用Φ表示

子串：串中任意个连续的字符组成的子序列

串是其自身的子串空串是任意串的子串

主串：包含子串的串

字符在串中的位置：字符在串中的序号

子串在主串中的位置：子串的第1个字符在主串中的位置

空格串：由一个或多个空格组成的串，其长度为空格个数

串相等：两个串长度相等且各个对应位置的字符也相等

2.ADT

ADT String { 数据对象：D={ai| ai CharacterSet, i=1,2,…,n, n0} 数据关系：R1={< ai-1 ，ai >｜ ai-1 , ai  D，i=2,3,…,n} 基本操作： StrAssign(&T, chars)； StrCopy(&T,S)； StrEmpty(S)； StrCompare(S,T)； StrLength(S)； ClearString(&S)； Concat(&T,S1,S2)； Substring(&Sub, S, pos,len)； Index(S,T,pos)； Replace(&S,T,V)； StrInsert(&S, pos, T)； StrDelete(&S, pos, len)； DestroyString(&S)；｝ADT String;

(2)基本操作 1.最小操作子集串赋值StrAssign串比较StrCompare求串长StrLength串联接Concat求子串SubString 2.其他操作串拷贝StrCopy串判空StrEmpty定位串Index串替换Replace串插入StrInsert串删除StrDelete串清空ClearString销毁串DestroyStr (3)串的表示方法 1.顺序存储结构

定长存储结构

特点：用长度固定的连续单元依次存储串值的字符序列以下标为０的数组分量存放实际串长——PASCAL串值后加一个不计入串长的结束标记字符——C、C++中用‘\0’作串的结束标记

堆分配存储结构

特点：采用动态字符数组存放串值，此时不必为数组预定义大小，以串长动态分配数组空间

数据类型定义

typedef struct { char *ch; int length; }HString; 2.链式存储结构

块链结构

数据类型定义

#define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; //串的头和尾指针，便于联结操作 int curlen; // 串的当前长度 } LString; (3)串的应用 1.文本编辑实质：修改字符数据的形式或格式基本操作：输入、查找、修改、删除、输出四、数组和广义表 (1)数组 1.数组的定义

ADT

ADT Array { 数据对象:ji=0, …, bi – 1, i = 1, 2, …, n, D={ | ∈ElemSet } 数据关系:R = {R1, R2, …, Rn} Ri={ |0 ≤ jk ≤ bk–1, 1 ≤ k ≤n且 k!=i, 0 ≤ ji ≤ bi–2, ∈D, i=1,2,…,n} 基本操作： InitArray(&A, n, bound1, …, boundn) DestroyArray(&A) Value(A, &e, index1, …, indexn) Assign(&A, e, index1, …, indexn) }ADT Array

n维数组是线性表的扩展

当n=1，n维数组退化成顺序表当n>1，n维数组可看成表中数据元素是n-1维数组的线性表 2.数组的顺序表示

因为数组一般不做插入/删除操作，所以用顺序结构表示数组是很自然的。

特点：用一组地址连续的存储单元按照某种规则存放数组中的数据元素。

2种顺序（顺序存储方式）

以行序为主（低下标优先法）以列序为主（高下标优先法）

元素地址的计算

要素

①数组的起始地址（即基地址）②数组维数和各维的长度；③数组中每个元素所占的存储单元

计算方法

二维

行主序：LOC(i,j) = LOC(0,0) + ( b2*i + j ) * L

列主序：LOC(i,j) = LOC(0,0) + ( b1*j + i ) * L

二维数组元素地址的通式

行优先存储时的地址公式为：

LOC(aij)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L

列优先存储的通式为：

LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

多维

设各维长度分别为b1, b2, b3, …, bn，每个元素占L个存储单元，起始地址是LOC(0,0,…,0)LOC (j1,j2,…,jn ) = LOC(0,0,…,0) + (b2b3…bn * j1+ b3b4*…bn * j2+ ……+ bnjn-1 + jn ) * L

随机存储结构

数组元素的存储位置是其下标的线性函数，由于计算各个元素存储位置的时间相等，所以存储数组中任一元素的时间也相等，具有这一特点的存储结构为随机存储结构。

实现

#define MAX_ARRAY_DIM 8 typedef struct { ElemType *base; //存储空间基址 int dim; //数组维数 int *bounds; //数组维界基址 int *constants; //数组映象函数常量{Ci}基址 } Array; 3.矩阵的压缩存储

压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：值相同的元素或零元素在矩阵中分布有一定规律。如三角矩阵、对角矩阵。

对称矩阵

n阶矩阵A中元素满足性质a[i][j]=a[j][i] (1 ≤i, j≤ n)

压缩存储

为每一对对称元素分配个存储空间. n2 n(n+1)/2 用行主序的下(上)三角阵来存储对称矩阵的元素。 sa[k](0 ≤ k ≤ n(n+1)/2-1) 为对称矩阵的压缩存储结构

上(下)三角阵

下(上)三角(不含对角线)元素为常数c或0的n阶矩阵

压缩存储

存储上(下)三角中的元素和常数c 用行主序存储上(下）三角阵的元素 sak 为上(下)三角阵的压缩存储结构

对角矩阵

所有非零元素都集中在以主对角线为中心的带状区域。其他元素为0。

压缩存储

用行主序存储带状区域的非0元素

稀疏矩阵：值相同的元素或零元素在矩阵中分布没有一定规律。

稀疏因子

设m行n列的矩阵含t个非零元素，定义δ=t/(m*n)为稀疏因子，则  0.05 的矩阵为稀疏矩阵。

稀疏矩阵的压缩存储

表示

三元组（ i，j，aij ）

三元组的C语言描述

typedef struct { int i,j; ElemType e; }Triple；

三元组顺序表的C语言描述

#define MAXSIZE 1250 typedef struct{ Triple data[MAXSIZE+1]; //data[0]未用 int mu,nu,tu; }TSMatrix；

行逻辑链接的顺序表

需求：随机存取任意一行的非0元方法：记住矩阵每一行第一个非0元在三元组顺序表中的位置设数组rpos[1…n]:矩阵中每行第一个非零元素的起始位置 rpos[1]=1; rpos[row]=rpos[row-1]+第row-1行的非零元素个数第i行所有非0元在data中的位置：rpos[i]…rpos[i+1]-1 行逻辑链接顺序表:在稀疏矩阵的三元组顺序表中设置指示行信息的辅助数组rpos typedef struct{ Triple data[MAXSIZE+1]; int rpos[MAXRC+1];//各行第1个非零元位置表，rpos[0]未用 int mu,nu,tu; }RLSMatrix；

十字链表

转置

稀疏矩阵转置方法一

Status TransposeSMatrix(TSMatrix M,TSMatrix &T) { T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) { q=1; for(col=1;col T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) { for(col=1;col

【本文地址】

【数据结构(C语言)】数据结构

【数据结构(C语言)】数据结构

今日新闻

推荐新闻