文章目录1、内容简介2、什么是交叉链表3、交叉链表应用4、交叉链表算法分析5、代码6的实现、截图7的执行、注意8、结束
1 .内容概要
主要介绍数据结构图存储结构之一的交叉链表的实现。
2、什么是交叉链接列表？ 交叉链表是指由图的邻接表和逆邻接表组合而成的存储结构。 (传送门：邻接表、邻接矩阵数据结构)
特点：来源于邻表，反邻表胜于它们。 十字链表将弧末尾节点相同的弧连接在一张链表上，弧开头节点相同的弧也连接在一张链表上。 同时，标头节点也发生了更改。 有第一个点和第一个点，还有指向其标头节点的指针字段。 这样就可以方便的知道那些边指向了目标节点啊，哪些边由此节点出发指向其他节点了。 这相当方便。
3、交叉链接列表APP :在一张地图上，我想知道从一个地方出发有多少个目的地，或者有多少个地方通向这里。 这个我们用交叉链表处理就容易了，只要追溯链表就行了。 例子列举得不好。 请谅解)
4 )交叉链表的算法分析与相邻表和反向相邻表的建立相同，我们的主要算法集中在输入数据后，根据弧的首尾节点进行节点的建立或连接操作。 具体实现可以看到以下代码(不难，有点麻烦)。
5、实现代码c代码：
# includeiostreamusingnamespacestd； ----------------十字链表存储结构的实现struct Arc *headarc，*tailarc； arc(intx，int y，struct Arc *p1=nullptr，struct Arc *p2=nullptr ) :tail(x )、head(y )、tail arc (P1 )、head(y 只需实现十字链表结构，无需对弧进行加权} Arc、*pArc； typedefstructtablehead {//intnum； pArc firIn，firOut； TableHead () {firIn=nullptr； firOut=nullptr； }} TableHead，TableHeadArray[MAXNUM]； 类d图形{ public : d图形(int y，int y ) :nodenum(x )，edgeNum(y ) {}int createList )； void显示列表() const； 隐私： table head array arr； 考虑初始化int nodeNum、edgeNum； (； int DGraph:createList () {cout输入末尾节点和开头节点进行圆弧(endl； int tailVertex，headVertex； pArc p1、p2； bool hsdhmg； for(intI=0，hsdhmg=false； i edgeNum； I ) {cin tailVertex headVertex； (p1=arr[tailVertex - 1].firOut )？ hs dhmg=true : (arr [ tail vertex-1 ].firout=newarc (tail vertex，headVertex，nullptr，nullptr )，p2=arr [ tai P1-tailarc=newarc(tailvertex，headVertex )； p2=p1-tailarc； hsdhmg=false； (}(p1=arr[headVertex - 1].firIn )？ hs dhmg=true : (arr [ head vertex-1 ].fir in=p2，1 )； if(HSDHMG ) while(P1-headarc ) p1=p1-headarc； p1-headarc=p2； hsdhmg=false； (} //headarc表示弧的第一个节点相同) }返回0； //ok } voiddgraph :3360显示列表() const {pArc p； bool hsdhmg； for(intj=0； j 2； j，coutendl(for ) intI=0； i nodeNum； I ) {cout i 1 ' -'； p=(arr[I].firout？ hsdhmg=false，ARR[I].firout:(HSdhmg=true，nullptr ) )； if () p=arr[I].firout )！=nullptr！ j ) while(p ) {cout p-head ' -'； p=p-tailarc； } cout 'null' endl； (else ) if ) hsdhmg ) {hsdhmg=false； cout 'null' endl； 继续； (if ) p=arr[I].firin ) while ) p ) {cout p-tail ' -'； p=p-headarc； } cout 'null' endl； }}}}int main () {int node，edge； cout '节点数和边缘数： '； cin node edge； dgraphg (节点，edge )； g .创建列表(； g .显示列表(； 返回0； (6、截图执行后是这样的。
链表按指出节点和指出节点的顺序用空格分隔打印。 (空间上方为指出节点，下方为输入节点)
7、请注意。 在相邻表的存储结构中，链表的节点表示节点，其中链表的节点表示圆弧。 这可以从结构体的定义中看出。
8、ending进度太慢了，要放下小事加快进度！ 加油~